Temu duga pengekodan: bagaimanakah anda melaksanakan automasi akhiran (suffix automaton) dan menerangkan keadaan klon?

Soalan

Diberi rentetan s, bina automasi akhiran (SAM) secara dalam talian (online). Laksanakan extend(c), terangkan len, link, peralihan, dan endpos, serta gunakan struktur tersebut untuk mengira substring yang berbeza, mengira kejadian corak, atau mencari substring sepunya terpanjang. Terangkan mengapa bilangan keadaan adalah O(n) dan bila klon diperlukan.

Perkara yang diuji oleh penemu duga

• Sama ada anda boleh menerangkan keadaan sebagai kelas kesetaraan endpos dan bukannya nod trie biasa.
• Sama ada anda membezakan cabang pautan langsung (direct-link), pautan punca (root-link), dan klon semasa pembinaan.
• Sama ada anda mengekalkan len[link[v]] < len[v], peralihan deterministik, dan invarian pokok pautan akhiran (suffix-link tree invariant).
• Sama ada anda boleh menukar invarian struktur kepada hasil pertanyaan dan kerumitan.

Contoh jawapan

SAM ialah DFA separa minimum yang mengenali setiap substring bagi rentetan sumber. Keadaan v menyimpan panjang maksimum yang diwakili len[v]; link[v] menunjuk kepada akhiran terpanjang dalam kelas kesetaraan yang lain. Keadaan ini mewakili selang berturutan (len[link[v]], len[v]], jadi satu keadaan boleh mewakili beberapa panjang substring.

Apabila sesuatu aksara ditambah di hujung, cipta cur dan telusuri pautan akhiran, sambil menambah peralihan yang tiada. Jika sasaran sedia ada q memenuhi len[p]+1 == len[q], pautkan cur terus ke q. Jika tidak, salin q ke dalam klon dengan len = len[p]+1, halakan semula peralihan yang berkaitan pada laluan pautan akhiran, dan halakan kedua-dua link[q] dan link[cur] ke klon tersebut. Klon ini memulihkan invarian panjang berturutan.

Setiap keadaan bukan punca menyumbang len[v] - len[link[v]] substring yang berbeza. Untuk mengira kejadian, mulakan satu untuk keadaan yang sepadan dengan awalan sumber, kemudian sebarkan kiraan ke pautan akhiran mengikut urutan len yang menurun.

Lakaran pelaksanaan

Pseudokod di bawah menunjukkan pembinaan; peralihan boleh menggunakan peta cincangan (hash map) atau peta tertib (ordered map).

extend(c):
  cur = new state
  len[cur] = len[last] + 1
  p = last
  while p != -1 and c not in next[p]:
    next[p][c] = cur
    p = link[p]
  if p == -1:
    link[cur] = root
  else:
    q = next[p][c]
    if len[p] + 1 == len[q]:
      link[cur] = q
    else:
      clone = copy(q)
      len[clone] = len[p] + 1
      while p != -1 and next[p][c] == q:
        next[p][c] = clone
        p = link[p]
      link[q] = link[cur] = clone
  last = cur

Jumlahkan len[v] - len[link[v]] ke atas keadaan bukan punca untuk mendapatkan kiraan substring yang berbeza. Untuk kiraan kejadian, ikuti peralihan ke keadaan corak dan baca kiraan yang disebarkan dalam urutan panjang yang menurun.

Perangkap biasa

• Menganggap SAM sebagai trie yang hanya menerima akhiran, dan bukannya pemampatan bagi semua kelas endpos.
• Menyalin peralihan klon tetapi membiarkan pautannya tidak konsisten, yang merosakkan selang panjang kemudian.
• Menghalakan semula terlalu sedikit peralihan kerana penelusuran pautan akhiran berhenti sebelum keadaan pertama yang tidak lagi menunjuk ke q.
• Mengira setiap klon sebagai kejadian awalan sumber, yang melambungkan semua kiraan kejadian.
• Menggunakan tatasusunan peralihan tetap untuk abjad yang besar tanpa menyatakan andaian memori dan pengekodannya.

Pertukaran kompromi kerumitan

Dengan abjad tetap atau peralihan dicincang, pembinaan mengambil masa dan ruang O(n), dengan paling banyak kira-kira 2n-1 keadaan. Peta peralihan tertib menambah faktor yang berkaitan dengan operasi abjad. SAM sangat sesuai untuk banyak pertanyaan substring pada satu teks tetap; tatasusunan akhiran (suffix arrays) boleh jadi lebih mudah dikawal untuk penelusuran leksikografi, kerja LCP, dan lokaliti cache.

Batas linear mengandaikan penambahan secara dalam talian (online appends). Menyisip atau memadam di tengah-tengah, atau mengemas kini kedua-dua hujung, memerlukan struktur yang berbeza; extend tidak boleh digunakan semula begitu sahaja sambil mengekalkan invariannya.

Mulakan dengan rentetan kosong, satu aksara, aksara berulang, dan input yang mencetuskan klon seperti abbb. Kemudian bandingkan rentetan rawak dengan set carian menyeluruh (brute-force) untuk kiraan substring berbeza dan kejadian. Untuk substring sepunya terpanjang, strimkan rentetan kedua melalui SAM dan ikuti pautan akhiran sekiranya berlaku ketidakpadanan.

Rujukan

• Nota SAM CP-algorithms: selang keadaan, pembinaan klon, dan formula pertanyaan.
• Kertas kerja automasi substring terkecil oleh Blumer et al.: batas teori bagi keadaan dan peralihan.
• Nota algoritma rentetan Carnegie Mellon: situasi apabila tatasusunan akhiran dan automasi akhiran lebih diutamakan.

Soalan susulan

Mengapakah setiap keadaan mewakili selang panjang yang berturutan?

Substring dalam satu kelas endpos membentuk jujukan panjang tanpa jurang. Pautan akhiran mengenal pasti kelas sempadan yang mengandungi akhiran wajar (proper suffix) terpanjang, jadi selangnya adalah tepat (len[link[v]], len[v]].

Bilakah klon diperlukan?

Jika sasaran sedia ada q mempunyai len[q] > len[p]+1, ia membawa dua julat panjang yang tidak berturutan. Menyalin peralihannya dan memisahkan klon memulihkan invarian tersebut.

Mengapakah jumlah selang mengira substring yang berbeza?

Selang keadaan adalah saling eksklusif (disjoint), dan setiap panjang yang diwakili sepadan dengan satu substring yang berbeza. Oleh itu, menjumlahkan saiz setiap selang mengira setiap substring bukan kosong yang berbeza tepat sekali.

Bagaimanakah SAM dan Aho–Corasick harus dibandingkan?

SAM mengindekskan semua substring bagi satu teks dan menyokong statistik agregat. Aho–Corasick mengindekskan set corak yang diketahui untuk pemadanan kelompok (batch matching). Sama ada teks atau set corak yang tetap biasanya menentukan pembinaan yang lebih baik.

Bagaimanakah anda mencari substring sepunya terpanjang?

Bina SAM untuk S, kemudian imbas T. Ikuti peralihan sambil menjejaki panjang padanan semasa; sekiranya berlaku ketidakpadanan, ikuti pautan akhiran dan cuba lagi. Simpan panjang maksimum yang diperhatikan.