Samanlıkta İğne: Şık Büyük Ölçekli Metin Arama Algoritması Eğitimi

"Metin arama" terimiyle karşılaşıldığında, genellikle, bir kullanıcı tarafından girildiğinde bir veya daha fazla arama terimini hızlı bir şekilde aramayı mümkün kılacak şekilde dizine alınmış büyük bir metin gövdesi akla gelir. Bu, bilgisayar bilimcileri için birçok çözümü bulunan klasik bir problemdir.

Ama nasıl bir ters senaryo? Ya önceden indeksleme için mevcut olan bir grup arama ifadesi ise ve yalnızca çalışma zamanında arama için büyük bir metin gövdesi sunuluyorsa? Bu sorular, bu veri yapısı öğreticisinin ele almaya çalıştığı şeydir.

Uygulamalar

Bu senaryo için gerçek bir dünya uygulaması, bir dizi tıbbi tezi bir tıbbi durum listesiyle eşleştirmek ve hangi tezlerin hangi koşulları tartıştığını bulmaktır. Başka bir örnek, geniş bir yargı içtihatları koleksiyonunu dolaşmak ve atıfta bulundukları yasaları çıkarmaktır.

Doğrudan yaklaşım

En temel yaklaşım, arama ifadeleri arasında döngü yapmak ve her bir ifadeyi tek tek metinde aramaktır. Bu yaklaşım iyi ölçeklenmiyor. Bir diğerinin içinde bir dize aramak, O(n) karmaşıklığına sahiptir. Bunu m arama ifadesi için tekrarlamak, korkunç O(m * n) ' ye yol açar.

Aşağıdaki C# snippet'inde görüldüğü gibi, uygulanması basit olan doğrudan bir yaklaşımın (muhtemelen yalnızca) üst tarafı:

 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;

Bu kodu geliştirme makinemde [1] bir test örneğine [2] karşı çalıştırarak, 1 saat 14 dakikalık bir çalışma süresi elde ettim - bir fincan kahve kapmak, kalkıp germek veya başka bir bahane için ihtiyacınız olan zamanın çok ötesinde geliştiriciler işi atlamak için kullanır.

Daha İyi Bir Yaklaşım - Trie

Önceki senaryo birkaç yolla geliştirilebilir. Örneğin, arama işlemi birden çok işlemci/çekirdeğe bölünebilir ve paralel hale getirilebilir. Ancak bu yaklaşımla elde edilen çalışma süresindeki azalma (4 işlemci/çekirdek üzerinde mükemmel bölünme varsayıldığında toplam 20 dakikalık çalışma süresi), kodlama/hata ayıklamaya eklenen karmaşıklığı haklı çıkarmaz.

Mümkün olan en iyi çözüm, metin gövdesini yalnızca bir kez geçen çözüm olacaktır. Bu, arama ifadelerinin, metin gövdesine paralel olarak, tek geçişte, O(n) nihai karmaşıklığına ulaşarak doğrusal olarak çaprazlanabilen bir yapıda indekslenmesini gerektirir.

Sadece bu senaryo için özellikle uygun olan bir veri yapısı trie . Bu çok yönlü veri yapısı genellikle göz ardı edilir ve konu arama sorunları olduğunda diğer ağaçla ilgili yapılar kadar ünlü değildir.

Toptal'ın denemelerle ilgili önceki öğreticisi, bunların nasıl yapılandırıldığına ve kullanıldığına dair mükemmel bir giriş sağlar. Kısacası, bir trie, kökten herhangi bir düğüme giden yolu izlemek, o dizinin geçerli bir alt kümesini verecek şekilde bir değerler dizisini depolayabilen özel bir ağaçtır.

Bu nedenle, tüm arama ifadelerini her düğümün bir kelime içerdiği tek bir denemede birleştirebilirsek, herhangi bir yoldan kökten aşağıya doğru izlemenin geçerli bir arama ifadesi verdiği bir yapıda düzenlenmiş cümlelere sahip olacağız.

Bir denemenin avantajı, arama süresini önemli ölçüde kısaltmasıdır. Bu trie öğreticisinin amaçları doğrultusunda kavramayı kolaylaştırmak için bir ikili ağaç düşünelim. İkili bir ağacın çaprazlanması, O(log 2 n) karmaşıklığına sahiptir, çünkü her düğüm ikiye bölünür ve kalan geçişi yarıya indirir. Bu nedenle, üçlü bir ağaç, O(log 3 n) geçiş karmaşıklığına sahiptir. Bununla birlikte, bir denemede, alt düğümlerin sayısı temsil ettiği sıra tarafından belirlenir ve okunabilir/anlamlı metin durumunda, alt düğümlerin sayısı genellikle yüksektir.

Metin Arama Algoritması

Basit bir örnek olarak, aşağıdaki arama ifadelerini varsayalım:

• "aynı aile"
• “farklı aile”
• "ayrı varoluş"
• "Lig üyeleri"

Arama ifadelerimizi önceden bildiğimizi unutmayın. Bu nedenle, bir deneme şeklinde bir dizin oluşturarak başlıyoruz:

Daha sonra, yazılımımızın kullanıcısı, ona aşağıdaki metni içeren bir dosya sunar:

Avrupa dilleri aynı ailenin üyeleridir. Ayrı varlıkları bir efsanedir.

Gerisi oldukça basit. Algoritmamızda, biri kökten başlayan veya trie yapımızdaki “start” düğümünden ve diğeri metin gövdesindeki ilk kelimede başlayan iki gösterge (isterseniz işaretçiler) olacaktır. İki gösterge kelime kelime birlikte hareket eder. Metin göstergesi basitçe ileriye doğru hareket ederken, trie göstergesi, eşleşen kelimelerin izini takip ederek trie'yi derinlemesine hareket ettirir.

Trie göstergesi iki durumda başa döner: Bir arama ifadesinin bulunduğu anlamına gelen bir dalın sonuna geldiğinde veya eşleşmeyen bir kelimeyle karşılaştığında, bu durumda eşleşme bulunamadı.

Metin göstergesinin hareketine ilişkin bir istisna, kısmi bir eşleşme bulunduğunda, yani bir dizi eşleşmeden sonra dal bitmeden önce eşleşmeyen bir durumla karşılaşılmasıdır. Bu durumda, son sözcük yeni bir dalın başlangıcı olabileceğinden, metin göstergesi ileriye taşınmaz.

Bu algoritmayı trie veri yapısı örneğimize uygulayalım ve nasıl gittiğini görelim:

Gördüğümüz gibi, sistem "aynı aile" ve "ayrı varlık" olmak üzere iki eşleşen ifadeyi başarıyla buluyor.

Gerçek Dünya Örneği

Yakın zamanda yaptığım bir proje için şu sorunla karşılaştım: Bir müşterinin kendi çalışma alanıyla ilgili çok sayıda makalesi ve doktora tezi var ve aynı alanla ilgili belirli başlıkları ve kuralları temsil eden kendi sözcük öbekleri listesini oluşturdu. İş.

İkilemi şuydu: İfadelerin listesi göz önüne alındığında, makaleleri/tezleri bu ifadelerle nasıl ilişkilendiriyor? Nihai hedef, rastgele bir grup kelime öbeği seçebilmek ve bu belirli ifadelerden bahseden makalelerin/tezlerin bir listesini anında kapmak için hazır hale getirmektir.

Daha önce tartışıldığı gibi, bu sorunu çözmenin iki kısmı vardır: Tümceleri bir denemede indekslemek ve gerçek arama. Aşağıdaki bölümler, C#'ta basit bir uygulama sağlar. Lütfen dosya işleme, kodlama sorunları, metin temizleme ve benzeri sorunların bu makalenin kapsamı dışında olduklarından bu parçacıklarda ele alınmadığını unutmayın.

indeksleme

İndeksleme işlemi, cümleleri birer birer çaprazlar ve bunları düğüm/seviye başına bir kelime olacak şekilde trie'ye ekler. Düğümler aşağıdaki sınıfla temsil edilir:

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

Her ifade, artan bir sayı kadar basit olabilen ve aşağıdaki indeksleme işlevine iletilen bir kimlik ile temsil edilir (değişken kökü, denemenin gerçek köküdür):

 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; } }

Aranıyor

Arama işlemi, yukarıdaki öğreticide tartışılan trie algoritmasının doğrudan bir uygulamasıdır:

 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); }

Verim

Burada sunulan kod, asıl projeden alınmıştır ve bu belgenin amacı doğrultusunda basitleştirilmiştir. Bu kodu aynı makinede [1] ve aynı test örneğine [2] karşı yeniden çalıştırmak, denemeyi oluşturmak için 2,5 saniye ve arama için 0,3 saniyelik bir çalışma süresi ile sonuçlandı. Mola zamanı için çok fazla, ha?

Varyasyonlar

Bu deneme eğitiminde açıklanan algoritmanın belirli uç durumlarda başarısız olabileceğini ve bu nedenle önceden tanımlanmış arama terimleri göz önünde bulundurularak tasarlandığını kabul etmek önemlidir.

Örneğin, bir arama teriminin başlangıcı, aşağıdaki gibi başka bir arama teriminin bir kısmıyla aynıysa:

• “arkadaşlarla paylaşmak ve eğlenmek için”
• “Biriyle paylaşmak için iki biletim var”

ve metin gövdesi, trie işaretçisinin yanlış yoldan başlamasına neden olan bir ifade içerir, örneğin:

Arkadaşlarla paylaşmak ve eğlenmek için iki biletim var.

o zaman algoritma herhangi bir terimle eşleşmede başarısız olacaktır, çünkü trie göstergesi, metin göstergesi metin gövdesinde eşleşen terimin başlangıcını geçene kadar başlangıç ​​düğümüne geri dönmeyecektir.

Algoritmayı uygulamadan önce bu tür bir uç durumun uygulamanız için bir olasılık olup olmadığını düşünmek önemlidir. Eğer öyleyse, algoritma, bir seferde yalnızca bir eşleşme yerine, herhangi bir zamanda tüm eşleşmeleri izlemek için ek trie göstergeleriyle değiştirilebilir.

Çözüm

Metin arama, bilgisayar biliminde derin bir alandır; sorunlar ve çözümlerle dolu bir alan. Başa çıkmam gereken veri türü (23 MB metin gerçek hayatta tonlarca kitaptır) nadir görülen bir durum veya özel bir sorun gibi görünebilir, ancak dilbilim araştırması, arşivleme veya diğer herhangi bir veri işleme türü ile çalışan geliştiriciler , düzenli olarak çok daha büyük miktarda veriyle karşılaşırsınız.

Yukarıdaki trie veri yapısı eğitiminde açıkça görüldüğü gibi, eldeki problem için doğru algoritmayı dikkatlice seçmek büyük önem taşımaktadır. Bu özel durumda, trie yaklaşımı, çalışma süresini bir saatten fazla olan bir saatten 3 saniyenin altına kadar şaşırtıcı bir şekilde %99,93 oranında kısalttı.

Bu hiçbir şekilde mevcut tek etkili yaklaşım değil, ancak yeterince basit ve işe yarıyor. Umarım bu algoritmayı ilginç bulmuşsunuzdur ve kodlama çalışmalarınızda size iyi şanslar dilerim.

[1] Bu test için kullanılan makine aşağıdaki özelliklere sahiptir:

• Intel i7 4700HQ
• 16 GB RAM

Test, Windows 8.1'de .NET 4.5.1 kullanılarak ve ayrıca Kubuntu 14.04'te mono'nun en son sürümü kullanılarak yapıldı ve sonuçlar çok benzerdi.

[2] Test örneği, toplam boyutu 23,5 MB ve metin gövdesi 1,5 MB olan 280K arama ifadesinden oluşur.