Temu duga pengekodan: Laksanakan pemadanan pelbagai corak Aho–Corasick

Prompt dan konteks

Ini adalah masalah pemadanan pelbagai corak untuk penapisan log, pengesanan perkataan sensitif, atau penyerlahan editor. Andaikan jumlah panjang kata kunci ialah M dan panjang teks ialah N; laporkan setiap permulaan padanan dan ID kata kunci. Kamus adalah tetap semasa pra-pemprosesan, teks mungkin panjang, dan penemu duga mengharapkan pra-pemprosesan, kerumitan imbasan, dan pengendalian pertindihan.

Perkara yang dinilai oleh penemu duga

Penemu duga mahu anda memperluaskan perkongsian awalan trie menjadi mesin keadaan terhingga (finite-state machine). Jawapan yang kukuh membina pautan kegagalan, mewarisi output di sepanjang pautan kegagalan, dan menerangkan sebab setiap aksara menyebabkan peralihan keadaan yang terbatas. Jawapan yang lemah menyatakan “gunakan trie” tetapi tidak dapat mengendalikan pertindihan akhiran atau pengunduran akibat ketidakpadanan.

Penjelasan untuk ditanya terlebih dahulu

• Adakah pemadanan peka huruf besar-kecil, dinormalkan Unicode, atau berasaskan bait? Definisi aksara mengubah trie dan unit kedudukan.
• Adakah padanan yang bertindih dan pelbagai kata kunci yang berakhir pada satu kedudukan mesti dikembalikan? Ini menentukan sama ada rantai output adalah lengkap.
• Adakah kamus kerap berubah? Kamus statik sesuai dengan satu automasi; kamus dinamik mungkin memerlukan pembinaan semula berversi.
• Adakah kedudukan dikira dalam aksara, bait, atau unit kod UTF-16? Padankan dengan kontrak pemanggil.
• Adakah teks tiba dalam bentuk ketulan (chunks)? Pengimbasan merentasi ketulan mesti mengekalkan keadaan dan bukannya menetapkan semula pada setiap ketulan.

Rangka kerja jawapan 30 saat

“Saya akan memasukkan setiap kata kunci ke dalam trie, kemudian menggunakan BFS untuk membina pautan kegagalan bagi setiap nod: akhiran terpanjang yang boleh digunakan selepas ketidakpadanan. Setiap nod menggabungkan output terminalnya sendiri dengan output daripada sasaran kegagalannya. Semasa mengimbas, ikuti peralihan atau pautan kegagalan dan pancarkan output nod semasa. Pra-pemprosesan adalah linear dalam jumlah panjang kata kunci ditambah perwakilan sisi; pengimbasan adalah O(N + padanan), dan input berketul hanya memerlukan keadaan automasi semasa.”

Jawapan mendalam langkah demi langkah

1. Bina trie. Setiap nod menyimpan sisi anak, pautan kegagalan, dan ID kata kunci. Nod terminal menambah ID; ia tidak boleh menyimpan satu ID sahaja.
2. Mulakan kegagalan. Anak terus daripada punca (root) gagal ke punca. Proses nod yang selebihnya mengikut kedalaman dengan baris gilir (queue).
3. Kira peralihan pengunduran. Untuk sisi daripada nod, ikuti pautan kegagalan induk sehingga sisi aksara yang sama ditemui; jika tidak kembali ke punca. Pengimbasan kemudiannya tidak akan membandingkan semula aksara teks terdahulu.
4. Agregat output. Salin output daripada sasaran kegagalan atau simpan pautan output untuk mengelakkan menyalin senarai; pautan output dilalui apabila melaporkan padanan.
5. Imbas teks. Cuba sisi anak untuk setiap aksara. Jika berlaku ketidakpadanan, ikuti pautan kegagalan sehingga sisi atau punca dicapai. Pancarkan setiap output pada nod baharu; permulaan ialah indeks semasa tolak panjang kata kunci tambah satu.
6. Kendalikan sempadan. Kata kunci yang bertindih dipancarkan secara semula jadi. Input berketul membawa keadaan antara ketulan. Jika padanan adalah terlalu besar, gunakan panggilan balik (callback), had, atau penomboran halaman (pagination) dan bukannya mengekalkan semua hasil O(padanan).

Gunakan peta cincangan (hash map) untuk abjad umum dan tatasusunan untuk abjad tetap yang kecil apabila memori mengizinkan. Bagi kamus yang berubah, bina versi baharu di latar belakang dan tukar pembaca secara atomik supaya imbasan tidak pernah melihat automasi separa.

Model jawapan

“Saya akan memasukkan semua kata kunci dan merekodkan setiap ID terminal, kemudian membina pautan kegagalan menggunakan BFS. Anak punca gagal ke punca. Untuk sisi lain, ikuti rantai kegagalan induk untuk mencari peralihan yang sama atau berundur ke punca. Output merangkumi ID terminal nod itu sendiri dan output kegagalan, jadi kedua-dua he dan she dipancarkan semasa mengimbas she. Setiap aksara teks mengikuti peralihan anak atau kegagalan, memberikan masa imbasan O(N + Z) dengan Z ialah bilangan padanan; pra-pemprosesan adalah O(M) ditambah storan sisi. Teks berketul mengekalkan keadaan, dan kemas kini kamus membina versi baharu sebelum beralih.”

Kesilapan lazim

• Kesilapan: Menggerakkan kedua-dua penunjuk dan teks ke belakang apabila berlaku ketidakpadanan → Sebab ia gagal: Ia merosot kepada pengimbasan semula untuk setiap kata kunci → Penyelesaian: Pautan kegagalan memastikan indeks teks kekal monotonik.
• Kesilapan: Menyimpan satu output sahaja bagi setiap nod → Sebab ia gagal: Kata kunci akhiran dan titik akhir yang dikongsi akan hilang → Penyelesaian: Gabungkan output kegagalan atau kekalkan pautan output.
• Kesilapan: Mendakwa pengimbasan sentiasa O(N) → Sebab ia gagal: Melaporkan padanan itu sendiri boleh menelan kos O(Z) → Penyelesaian: Nyatakan O(N + Z) dan strim output.
• Kesilapan: Menetapkan semula ke punca pada setiap ketulan → Sebab ia gagal: Kata kunci yang merentasi ketulan tidak dapat dipadankan → Penyelesaian: Bawa keadaan automasi antara ketulan.

Soalan susulan dan jawapan

Mengapa tidak menjalankan KMP secara berasingan untuk setiap kata kunci?

Larian KMP yang berasingan memerlukan O(KN) imbasan teks. Aho–Corasick berkongsi awalan trie dan memproses teks sekali sahaja, yang sesuai untuk kamus tetap dan teks yang panjang.

Mengapa pautan kegagalan menemui setiap padanan?

Ia menunjuk kepada akhiran terpanjang yang boleh digunakan. Meneruskan di sepanjang rantai kegagalan menyenaraikan setiap akhiran yang juga merupakan awalan kata kunci, jadi pengagregatan output menemui padanan bersarang dan bertindih.

Bagaimana jika peta cincangan anak kehabisan memori?

Pilih tatasusunan untuk abjad kecil, jadual sisi padat, atau double-array trie, dan gunakan pautan output untuk mengelakkan menyalin senarai. Ukur kiraan nod dan sisi sebelum memampatkan.

Bolehkah kamus kerap berubah?

Versikan kamus, bina automasi baharu di latar belakang, sahkannya, dan gantikan penunjuk pembaca secara atomik. Kekalkan versi lama seketika untuk strim yang sedang berjalan.