텍스트의 모든 키워드를 찾는 효율적인 알고리즘

Question

많은 철자로 텍스트가 포함 된 많은 문자열이 있습니다. 키워드를 검색하여 이러한 문자열을 토큰 화하고 키워드가 발견되면 해당 키워드에 대해 관련 텍스트를 사용합니다.

검색 문자열에 "schw.", "schwa"라는 텍스트가 포함될 수 있습니다. 및 "schwarz". 세 단어가 모두 "schwarz"라는 텍스트로 해석됩니다.

이제 모든 단일 키워드에 대해 string.Contains (키워드)를 수행하지 않고 모든 키워드를 찾는 효과적인 방법을 찾고 있습니다.

샘플 데이터 :

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 

샘플 키워드 (키, 값) :

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 

샘플 결과 :

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

이 "Algorithms using finite set of patterns"

맞는 것 같다

Aho–Corasick string matching 알고리즘은 Alfred V. Aho 및 Margaret J. Corasick에 의해 발명 된 알고리즘 검색 알고리즘입니다. 사전 일치 알고리즘 인 은 문자열 ("사전")의 유한 집합의 요소를 입력 텍스트 내에 배치합니다. 이는 모든 패턴 을 "즉시"와 일치 시키므로 알고리즘의 복잡도는 길이의 패턴과 검색된 텍스트의 길이에 출력 매치의 수를 더한 선형입니다. 개의 일치 항목이 모두 있기 때문에 부분 문자열 (예 : dictionary = a, aa, aaa, aaaa 및 입력 문자열이 aaaa) 인 경우 개의 일치하는 2 차 일치 수가있을 수 있습니다. Rabin–Karp algorithm

은 텍스트 패턴 문자열 세트 중 하나를 찾기 위해 해싱 용도 1,987 마이클 O. 라빈와 Richard M. 카프에 의해 생성 된 문자열 검색 알고리즘이다. 길이가 n이고 p 패턴이 결합 길이가 m 인 텍스트의 경우, 평균 및 최고 사례 실행 시간은 공간 O (p)에서 O (n + m)이지만 최악의 경우 시간은 O (nm) . 대조적으로, Aho-Corasick 문자열 매칭 알고리즘은 점근적인 최악의 시간 복잡도 O (n + m)의 공간 O (m)에 있습니다.

Answer 2

나는 방법을 제안한다

1) 키의 사전에 string.Split과 일치를 사용하여 Tokenise 당신이

2

이) 자신 tokeniser 그것은에 문자를 추가 ReadToken() 방법으로 독자를 구현 버퍼가 발견 될 때까지 (스플릿은이를 수행 할 수 있음) 분할 문자를 출력하고이를 토큰으로 출력합니다. 다음 당신은 당신의 사전에 대하여 검사한다.

Answer 3

어쩌면 조금 힘이 들지만 어쩌면 ANTLR을 살펴보아야합니다.

Answer 4

당신은 당신이 (F) 렉스,

Answer 5

re2c 또는 ragel 내가 일치하는 키워드의 각 그룹에 대해 미리 컴파일 된 정규 표현식을 사용하는 것이 사용할 수있는 키워드의 고정 세트가있는 경우. 백그라운드에서 이것들은 유한 오토 마타에 "컴파일"되므로 문자열의 패턴을 인식하는 데 꽤 빠르며 각각의 가능한 문자열에 대해 Contains보다 훨씬 빠릅니다.

사용 : System.Text.RegularExpressions. 당신의 예에서

". 슈"

• ". schw" 와 "슈왈츠는"여기에 해당
• new Regex(@"schw(a?\.|arz)", RegexOptions.Compiled)

또한 문서 : http://msdn.microsoft.com/en-us/library/system.text.regularexpressions.regexoptions(v=VS.90).aspx