Bir metindeki tüm anahtar kelimeleri bulmak için verimli algoritma

Question

Çok sayıda farklı yazımda metin içeren çok sayıda dizim var. Anahtar kelimeler arayarak bu dizeleri belirteçlerimdir ve bir anahtar kelime bulunursa, bu anahtar kelime için birleşik bir metin kullanırım.

Arama dizesinin "schw.", "Schwa." ve "schwarz". Tüm "schwarz" metninde çözülen üç anahtar kelime var.

Şimdi, anahtar sözcükler olmadan tüm anahtar kelimeleri bulmanın etkili bir yolunu arıyorum.İstediğiniz her anahtar kelime için (anahtar kelime).

Örnek veri:

H-Fuss ahorn 15 cm/SH48cm 
Metall-Fuss chrom 9 cm/SH42cm 
Metall-Kufe alufbg.12 cm/SH45c 
Metall-Kufe verchr.12 cm/SH45c 
Metall-Zylind.aluf.12cm/SH45cm 
Kufe alufarbig 
Metall-Zylinder hoch alufarbig 
Kunststoffgl.schw. - hoch 
Kunststoffgl.schw. - Standard 
Kunststoffgleiter - schwarz für Sitzhoehe 42 cm 

örnek anahtar kelimeler (anahtar, değer):

h-fuss, Holz 
ahorn, Ahorn 
metall, Metall 
chrom, Chrom 
verchr, Chrom 
alum, Aluminium 
aluf, Aluminium 
kufe, Kufe 
zylind, Zylinder 
hoch, Hoch 
kunststoffgl, Gleiter 
gleiter, Gleiter 
schwarz, Schwarz 
schw., Schwarz 

Numune sonucu:

Holz, Ahorn 
Metall, Chrom 
Metall, Kufe, Aluminium 
Metall, Kufe, Chrom 
Metall, Zylinder, Aluminium 
Kufe, Aluminium 
Metall, Zylinder, Hoch, Aluminium 
Gleiter, Schwarz, Hoch 
Gleiter, Schwarz 
Gleiter, Schwarz 

Answer 1

Bu "Algorithms using finite set of patterns"

uygun görünüyor

Aho–Corasick string matching algoritması, Alfred V. Aho ve Margaret J. Corasick tarafından icat edilen algoritmasını araştıran bir dizedir. Bu bir giriş metin içinde dizeleri ("Sözlük") sonlu kümesinin elemanları bulur sözlük eşleştirme algoritması bir tür olduğunu. "bir kerede" tüm desenleriyle eşleşir, bu nedenle algoritmasının karmaşıklığı modelinin uzunluğuna ve arama metninin uzunluğunun yanı sıra çıkış eşleşmelerinin uzunluğuna doğrusaldır. Tüm eşleşmeleri bulunduğundan, her bir alt dizgenin eşleşmesi durumunda karesel sayı eşleşmesi olabileceğini unutmayın (ör. Sözlüğü = a, aa, aaa, aaaa ve giriş dizesi aaaa'dır). Rabin–Karp algorithm

bir metinde desen dizeleri bir kümesinin herhangi birini bulmak için karma kullanır 1987 Michael O. Rabin ve Richard M. Karp tarafından oluşturulan bir dize arama algoritmasıdır. n uzunluğundaki p ve kombine uzunluğundaki n ve p desenleri için, ortalama ve en iyi durum çalışma süresi uzayında O (p) O (p) iken, en kötü durum zamanı O (nm) . Buna karşılık, Aho – Corasick dizgi eşleme algoritması O (m) uzayında asimptotik en kötü zaman karmaşıklığı O (n + m) değerine sahiptir.

Answer 2

Ben yaklaşımlar önermek:

1) anahtarlarının bir Dictionary karşı string.Split ve eşleme kullanarak Tokenise Eğer var) kendiniz tokeniser bir karakter ekler ReadToken() yöntemi ile bir okuyucu uygulamak Arabellek bulana kadar (Bölünmüş yapabilir) bölünmüş bir karakter ve çıktı olarak belirteci olarak çıkarır. Ardından sözlüğünüze karşı kontrol edin.

Answer 3

Belki de biraz üst üste geliyor ama kesinlikle ANTLR numaralı telefonu incelemelisiniz.

Answer 4

Eğer (f) Lex

Answer 5

re2c veya ragel Ben maç için anahtar kelime her grup için önceden derlenmiş düzenli ifadeler kullanmak istiyorsunuz kullanabilirsiniz anahtar kelime sabit bir dizi var. Arka planda, bunlar sonlu automata için "derlenmiştir", bu yüzden dizinizdeki deseni tanımak için oldukça hızlıdır ve olası dizilerin her biri için Contains'dan çok daha hızlıdır.

şu numarayı kullanır: System.Text.RegularExpressions. Örnekte

: "schwa"

• "schw", ve "schwarz" burada mevcut
• new Regex(@"schw(a?\.|arz)", RegexOptions.Compiled)

Daha belgeleri: http://msdn.microsoft.com/en-us/library/system.text.regularexpressions.regexoptions(v=VS.90).aspx