Uygulanmasında anahtar kelime karşılaştırma şeması (ters arama)

6 Cevap php

Ben anahtar kelime sürekli büyüyen bir veritabanı var. Gelen metin girişleri (makaleler, yemler vb) ayrıştırmak ve metinde mevcut veritabanından hangi anahtar kelimeleri bulmak gerekir. Anahtar kelime veritabanı metin daha büyüktür.

Veritabanı sürekli (kullanıcılar izlemek için daha fazla anahtar kelime eklemek) büyüyor beri, ben iyi seçenek kelimelere metin girişini kırmak ve veritabanı karşı olanlar karşılaştırabilirsiniz olacak rakam. Benim ana ikilem bu karşılaştırma düzeni (PHP ve MySQL bu proje için kullanılacaktır) uygulamaktadır.

En naif uygulaması tüm bulundu kelimeleri listeleyen tümcesi devi ile, anahtar kelimeler tabloya karşı basit bir SELECT sorgusu oluşturmak olacaktır.

SELECT user_id,keyword FROM keywords WHERE keyword IN ('keyword1','keyword2',...,'keywordN');

Başka bir yaklaşım (memcache gibi bir şey kullanarak) bellekte bir karma-tablo oluşturmak olacaktır ve aynı şekilde buna karşı kontrol edin.

Herkes arama bu tür herhangi bir deneyime sahiptir ve daha iyi nasıl uygulanacağı konusunda herhangi bir öneriniz var mı? Ben sadece bu noktada fikirler topluyorum, henüz bu yaklaşımların hiçbirini denemedim.

6 Cevap

Birden fazla anahtar kelime için bir metin akışı arama klasik yolu aranacak metinde zaman doğrusal kullandığı Aho-Corasick finite automaton, olduğunu. Eğer küçük uyarlamalar tek kelime sınırları dizeleri tanımak, ya da belki de sadece bulunan anahtar kelimeleri kontrol ve daha büyük deyişle gömülü olmadığından emin olmak için basit olurdu isteyeceksiniz.

Sen fgrep bir uygulama bulabilirsiniz. Daha da iyisi, Preston Briggs bahsediyorsun sen anahtar kelime arama tam tür yok C oldukça güzel bir uygulama yazdı. (Bu 'ilginç' kimlikleri 'geçtiği için programlar arar.) Preston uygulaması Noweb literate-programming tool parçası olarak dağıtılır. Sen --- PHP bu kodu aramak için ya da PHP ile yeniden bir yolunu bulabiliriz C yaklaşık 220 hatları kendisini tanımak ve ana program başka 135 satır.

Önerilen bütün çözeltiler, including-Aho Corasick, ortak olarak, bu özelliklere sahiptir:

  • Veritabanında anahtar kelime sayısına zaman ve uzay orantılı alan bir ön işleme aşaması.

  • Metin artı bulunan anahtar kelime sayısının uzunluğuna zaman ve uzay orantılı alan bir arama adım.

Aho-Corasick arama adım orantılılık oldukça iyi sabitler sunuyor, ama metinler küçük ise, bu önemli değildir. Metinler küçük ve veritabanı büyükse aslında, muhtemelen ön işleme aşamasında kullanılan bellek miktarını en aza indirmek istiyoruz. Andrew Appel DAWG veri yapısı the world's fastest scrabble program muhtemelen hile yapacak.

Genel olarak,

  1. kelimelerle metni kırmak

    b. geri kanonik kök forma kelime dönüştürmek

    c. Ortak bağlaç sözcükleri bırakın

    d. şerit çiftleri

  2. insert the words into a temporary table then do an inner join against the keywords table, or (as you suggested) build the keywords into a complex query criteria

Bu 3 önbelleğe için faydalı olabilir - önceden filtre potansiyel anahtar kelimeler veya 4 harfli karma dizi; bellek boyutu ve etkinliği arasındaki en iyi dengeyi bulmak için denemeniz gerekir.

Ben size soruyoruz ne% 100 net değilim, ama belki ne arıyorsanız bir inverted index nedir?

Güncelleme:

Bir kerede birden fazla anahtar kelime maç için ters bir dizin kullanabilirsiniz.

Belirteçleri içine yeni bir belge bölmek ve ters endeksi tabloya belge için bir tanımlayıcı ile eşleştirilmiş belirteçleri yerleştirin. A (yerine denormalized) ters endeksi tablosu:

inverted_index
-----
document_id keyword

El 3 anahtar kelime arıyorsanız:

select document_id, count(*) from inverted_index
  where keyword in (keyword1, keyword2, keyword3)
  group by document_id 
  having count(*) = 3

Eğer umurumda anahtar kelimelerin bir tablo varsa, sadece iç değil, bir in () işlemi daha join kullanın:

keyword_table
----
keyword othercols

select keyword_table.keyword, keyword_table.othercols from inverted_index 
   inner join keyword_table on keyword_table.keyword=inverted_index.keyword
   where inverted_index.document_id=id_of_some_new_document

yakın ne istediğinizi, bu herhangi bir?

Böyle Sphinx gibi bir tam metin çözüm mezun düşündünüz mü?

Ben kendim kullanmadım, çünkü burada benim şapkadan bahsediyorum. Ama yüksek hızda tam arama çözümü olarak ilgi çok oluyor. Muhtemelen kullandığınız herhangi bir ilişkisel bir çözüm daha iyi dönüşebilecek.

İşte blog MySQL bir metin arama çözüm olarak Sfenks kullanarak ilgili.

Ben burada 2 şey yapardı.

İlk (ve bu doğrudan soru ile ilgili değildir) I kullanıcılar tarafından break up ve bölme kullanıcı anahtar kelimeler ediyorum. Kullanıcı dilimleri veya aralıkları farklı dilimler mevcut dağıtılan aramaları için ideal farklı sunucular üzerinde daha az veri ile daha fazla tablo olması. Aka, UserA'ın tüm verileri dilim biri, vb dilim iki, on UserB üzerinde var

İkincisi, ben anahtar kelime varlığını belirlemek için bellek karma tablo çeşit olurdu. Bu büyük olasılıkla aramalarını dağıtmak için de federasyon olacaktır. N Anahtar kelime varlığı sunucular için, anahtar kelime karma ve sonra memcached sunucuların tamamında bu tuşların aralıkları dağıtmak n bunu mod. Bu hızlı yolu olduğunu söylüyorlar sağlar anahtar kelime x bunu karma ve would üzerinde yaşamak ne sunucu belirlemek, izleniyor. Sonra arama yapmak ve toplam anahtar kelimeler izleniyor / toplamak.

Bu noktada en azından anahtar kelimeler izleniyorsa hangi bileceksiniz ve size kullanıcı dilimleri almak ve kullanıcıların hangi anahtar izleme hangi belirlemek için sonraki aramaları gerçekleştirebilir.

Kısacası: SQL is not an ideal solution here.

Ben (Scrabble kağıdı başvuran yukarıda önerilen gibi) ben ilk prensiplerden yazdı ve ben AHO algoritma veya değil gibi bir şey olup olmadığını bilmiyorum ancak bir dostum kullanarak birden fazla anahtar kelime için tarama için bazı kodlar kadar hacklendi.

http://www.gtoal.com/wordgames/spell/multiscan.c.html

Ben ilk Wordgame programcılar posta listesinde yayınlandıktan sonra bir arkadaşım benim kod bazı kesmek yapılmış ve onun sürüm muhtemelen daha verimli:

http://www.gtoal.com/wordgames/spell/multidawg.c.html

Oldukça iyi teraziler ...

G

etiketler