Needle in a Haystack: Tutorial Algoritma Pencarian Teks Skala Besar yang Bagus

Ketika menemukan istilah “pencarian teks”, orang biasanya berpikir tentang sekumpulan besar teks yang diindeks sedemikian rupa sehingga memungkinkan untuk dengan cepat mencari satu atau lebih istilah pencarian saat dimasukkan oleh pengguna. Ini adalah masalah klasik bagi para ilmuwan komputer, yang memiliki banyak solusi.

Tapi bagaimana dengan skenario sebaliknya? Bagaimana jika apa yang tersedia untuk pengindeksan sebelumnya adalah sekelompok frase pencarian, dan hanya pada saat runtime adalah teks besar yang disajikan untuk pencarian? Pertanyaan-pertanyaan inilah yang coba dijawab oleh tutorial struktur data trie ini.

Aplikasi

Aplikasi dunia nyata untuk skenario ini adalah mencocokkan sejumlah tesis medis dengan daftar kondisi medis dan mencari tahu tesis mana yang membahas kondisi mana. Contoh lain adalah melintasi banyak koleksi preseden peradilan dan mengekstraksi undang-undang yang mereka rujuk.

Pendekatan langsung

Pendekatan yang paling dasar adalah untuk mengulang melalui frase pencarian, dan mencari melalui teks setiap frase, satu per satu. Pendekatan ini tidak berskala dengan baik. Mencari string di dalam string lain memiliki kompleksitas O(n) . Mengulanginya untuk m frasa pencarian mengarah ke O(m * n) yang mengerikan.

Keuntungan (mungkin saja) dari pendekatan langsung yang mudah diterapkan, seperti yang terlihat dalam cuplikan C# berikut:

 String[] search_phrases = File.ReadAllLines ("terms.txt"); String text_body = File.ReadAllText("body.txt"); int count = 0; foreach (String phrase in search_phrases) if (text_body.IndexOf (phrase) >= 0) ++count;

Menjalankan kode ini di mesin pengembangan saya [1] terhadap sampel uji [2], saya mendapatkan waktu proses 1 jam 14 menit – jauh melampaui waktu yang Anda perlukan untuk minum secangkir kopi, bangun dan meregangkan tubuh, atau alasan lainnya pengembang gunakan untuk melewatkan pekerjaan.

Pendekatan yang Lebih Baik - The Trie

Skenario sebelumnya dapat ditingkatkan dalam beberapa cara. Misalnya, proses pencarian dapat dipartisi dan diparalelkan pada beberapa prosesor/inti. Tetapi pengurangan runtime yang dicapai dengan pendekatan ini (runtime total 20 menit dengan asumsi pembagian sempurna lebih dari 4 prosesor/core) tidak membenarkan kompleksitas tambahan untuk pengkodean/debugging.

Solusi terbaik yang mungkin adalah solusi yang melintasi badan teks hanya sekali. Ini membutuhkan frasa pencarian untuk diindeks dalam struktur yang dapat ditransverskan secara linier, paralel dengan badan teks, dalam satu lintasan, mencapai kompleksitas akhir O(n) .

Struktur data yang sangat cocok untuk skenario ini adalah trie . Struktur data serbaguna ini biasanya diabaikan dan tidak setenar struktur terkait pohon lainnya dalam hal masalah pencarian.

Tutorial Toptal sebelumnya tentang percobaan memberikan pengenalan yang sangat baik tentang bagaimana mereka terstruktur dan digunakan. Singkatnya, trie adalah pohon khusus, yang mampu menyimpan urutan nilai sedemikian rupa sehingga menelusuri jalur dari root ke simpul mana pun menghasilkan subset yang valid dari urutan itu.

Jadi, jika kita dapat menggabungkan semua frase pencarian menjadi satu trie, di mana setiap node berisi sebuah kata, kita akan memiliki frase yang diletakkan dalam struktur di mana hanya menelusuri dari akar ke bawah, melalui jalur apapun, menghasilkan frase pencarian yang valid.

Keuntungan dari trie adalah memangkas waktu pencarian secara signifikan. Agar lebih mudah dipahami untuk keperluan tutorial trie ini, mari kita bayangkan sebuah pohon biner. Melintasi pohon biner memiliki kompleksitas O(log 2 n) , karena setiap simpul bercabang menjadi dua, memotong lintasan yang tersisa menjadi dua. Dengan demikian, pohon terner memiliki kompleksitas traversal O(log 3 n) . Namun, dalam suatu percobaan, jumlah simpul anak ditentukan oleh urutan yang diwakilinya, dan dalam kasus teks yang dapat dibaca/bermakna, jumlah anak biasanya tinggi.

Algoritma Pencarian Teks

Sebagai contoh sederhana, mari kita asumsikan frasa pencarian berikut:

• “keluarga yang sama”
• “keluarga yang berbeda”
• “keberadaan terpisah”
• “anggota liga”

Ingatlah bahwa kami mengetahui frasa pencarian kami sebelumnya. Jadi, kita mulai dengan membangun indeks, dalam bentuk trie:

Kemudian, pengguna perangkat lunak kami menyajikannya dengan file yang berisi teks berikut:

Bahasa-bahasa Eropa adalah anggota dari keluarga yang sama. Keberadaan mereka yang terpisah adalah sebuah mitos.

Selebihnya cukup sederhana. Algoritme kami akan memiliki dua indikator (penunjuk, jika Anda suka), satu dimulai dari akar, atau simpul "mulai" dalam struktur trie kami, dan yang lainnya pada kata pertama di badan teks. Kedua indikator bergerak bersama, kata demi kata. Indikator teks hanya bergerak maju, sedangkan indikator trie melintasi trie secara mendalam, mengikuti jejak kata-kata yang cocok.

Indikator trie kembali untuk memulai dalam dua kasus: Saat mencapai akhir cabang, yang berarti frasa pencarian telah ditemukan, atau ketika menemukan kata yang tidak cocok, dalam hal ini tidak ada kecocokan yang ditemukan.

Satu pengecualian untuk pergerakan indikator teks adalah ketika kecocokan sebagian ditemukan, yaitu setelah serangkaian kecocokan, ketidakcocokan ditemukan sebelum cabang berakhir. Dalam hal ini indikator teks tidak bergerak maju, karena kata terakhir bisa menjadi awal dari cabang baru.

Mari kita terapkan algoritme ini ke contoh struktur data trie kita dan lihat bagaimana hasilnya:

Seperti yang dapat kita lihat, sistem berhasil menemukan dua frasa yang cocok, "keluarga yang sama" dan "keberadaan terpisah" .

Contoh dunia nyata

Untuk proyek baru-baru ini, saya dihadapkan dengan masalah berikut: klien memiliki sejumlah besar artikel dan tesis PhD yang berkaitan dengan bidang pekerjaannya, dan telah membuat daftar frasa sendiri yang mewakili judul dan aturan spesifik yang berkaitan dengan bidang yang sama. kerja.

Dilemanya adalah ini: mengingat daftar frasanya, bagaimana dia menautkan artikel/tesis ke frasa itu? Tujuan akhirnya adalah untuk dapat memilih sekelompok frasa secara acak dan segera memiliki daftar artikel/tesis yang menyebutkan frasa tertentu yang siap untuk diambil.

Seperti yang telah dibahas sebelumnya, ada dua bagian untuk memecahkan masalah ini: Mengindeks frasa menjadi trie, dan pencarian aktual. Bagian berikut memberikan implementasi sederhana dalam C#. Harap perhatikan bahwa penanganan file, masalah penyandian, pembersihan teks, dan masalah serupa tidak ditangani dalam cuplikan ini, karena berada di luar cakupan artikel ini.

pengindeksan

Operasi pengindeksan hanya melintasi frase satu per satu dan memasukkannya ke dalam trie, satu kata per node/level. Node diwakili dengan kelas berikut:

 class Node { int PhraseId = -1; Dictionary<String, Node> Children = new Dictionary<String, Node>(); public Node() { } public Node(int id) { PhraseId = id; } }

Setiap frase diwakili oleh ID, yang dapat sesederhana nomor tambahan, dan diteruskan ke fungsi pengindeksan berikut (akar variabel adalah akar sebenarnya dari trie):

 void addPhrase(ref Node root, String phrase, int phraseId) { // a pointer to traverse the trie without damaging // the original reference Node node = root; // break phrase into words String[] words = phrase.Split (); // start traversal at root for (int i = 0; i < words.Length; ++i) { // if the current word does not exist as a child // to current node, add it if (node.Children.ContainsKey(words[i]) == false) node.Children.Add(words[i], new Node()); // move traversal pointer to current word node = node.Children[words[i]]; // if current word is the last one, mark it with // phrase Id if (i == words.Length - 1) node.PhraseId = phraseId; } }

mencari

Proses pencarian adalah implementasi langsung dari algoritma trie yang dibahas dalam tutorial di atas:

 void findPhrases(ref Node root, String textBody) { // a pointer to traverse the trie without damaging // the original reference Node node = root; // a list of found ids List<int> foundPhrases = new List<int>(); // break text body into words String[] words = textBody.Split (); // starting traversal at trie root and first // word in text body for (int i = 0; i < words.Length;) { // if current node has current word as a child // move both node and words pointer forward if (node.Children.ContainsKey(words[i])) { // move trie pointer forward node = node.Children[words[i]]; // move words pointer forward ++i; } else { // current node does not have current // word in its children // if there is a phrase Id, then the previous // sequence of words matched a phrase, add Id to // found list if (node.PhraseId != -1) foundPhrases.Add(node.PhraseId); if (node == root) { // if trie pointer is already at root, increment // words pointer ++i; } else { // if not, leave words pointer at current word // and return trie pointer to root node = root; } } } // one case remains, word pointer as reached the end // and the loop is over but the trie pointer is pointing to // a phrase Id if (node.PhraseId != -1) foundPhrases.Add(node.PhraseId); }

Pertunjukan

Kode yang disajikan di sini diambil dari proyek sebenarnya dan telah disederhanakan untuk tujuan dokumen ini. Menjalankan kode ini lagi pada mesin yang sama [1] dan terhadap sampel uji yang sama [2] menghasilkan runtime 2,5 detik untuk membangun trie dan 0,3 detik untuk pencarian. Begitu banyak untuk waktu istirahat, eh?

Variasi

Penting untuk diketahui bahwa algoritme seperti yang dijelaskan dalam tutorial trie ini dapat gagal dalam kasus tepi tertentu, dan oleh karena itu dirancang dengan istilah pencarian yang telah ditentukan sebelumnya.

Misalnya, jika awal dari satu istilah pencarian identik dengan beberapa bagian dari istilah pencarian lainnya, seperti pada:

• “ untuk berbagi dan menikmati dengan teman-teman”
• “Saya punya dua tiket untuk dibagikan dengan seseorang”

dan isi teks berisi frasa yang menyebabkan penunjuk trie memulai jalur yang salah, seperti:

Saya memiliki dua tiket untuk dibagikan dan dinikmati bersama teman-teman.

maka algoritme akan gagal mencocokkan istilah apa pun, karena indikator trie tidak akan kembali ke simpul awal sampai indikator teks telah melewati awal istilah yang cocok di badan teks.

Penting untuk mempertimbangkan apakah kasus tepi semacam ini memungkinkan untuk aplikasi Anda sebelum menerapkan algoritme. Jika demikian, algoritme dapat dimodifikasi dengan indikator trie tambahan untuk melacak semua kecocokan pada waktu tertentu, bukan hanya satu kecocokan pada satu waktu.

Kesimpulan

Pencarian teks adalah bidang yang mendalam dalam ilmu komputer; bidang yang kaya dengan masalah dan solusi yang sama. Jenis data yang harus saya tangani (23MB teks adalah satu ton buku dalam kehidupan nyata) mungkin tampak seperti kejadian langka atau masalah khusus, tetapi pengembang yang bekerja dengan penelitian linguistik, pengarsipan, atau jenis manipulasi data lainnya , menemukan jumlah data yang jauh lebih besar secara teratur.

Seperti yang terlihat dalam tutorial struktur data trie di atas, sangat penting untuk hati-hati memilih algoritme yang benar untuk masalah yang dihadapi. Dalam kasus khusus ini, pendekatan trie memotong runtime dengan mengejutkan 99,93%, dari lebih dari satu jam menjadi kurang dari 3 detik.

Ini bukan satu-satunya pendekatan yang efektif di luar sana, tetapi cukup sederhana, dan berhasil. Saya harap Anda menganggap algoritme ini menarik, dan semoga Anda beruntung dalam upaya pengkodean Anda.

[1] Mesin yang digunakan untuk pengujian ini memiliki spesifikasi sebagai berikut:

• Intel i7 4700HQ
• RAM 16GB

Pengujian dilakukan pada Windows 8.1 menggunakan .NET 4.5.1 dan juga Kubuntu 14.04 menggunakan versi terbaru dari mono dan hasilnya sangat mirip.

[2] Sampel uji terdiri dari 280 ribu frasa penelusuran dengan ukuran total 23,5 MB, dan isi teks 1,5 MB.