algoritmo eficiente para encontrar todas las palabras clave en un texto

Question

que tiene una gran cantidad de cadenas que contienen texto en un montón de diferentes grafías. Estoy tokenizando estas cadenas buscando palabras clave y, si se encuentra una palabra clave, utilizo un texto asociado para esa palabra clave.

Digamos que la cadena de búsqueda puede contener el texto "Schw.", "Schwa". y "schwarz". Tengo tres palabras clave que todas resuelven el texto "schwarz".

Ahora estoy en busca de una forma efectiva para encontrar todas las palabras clave sin hacer un string.Contains (palabra clave) para cada palabra clave.

datos de la muestra:

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 

Ejemplos de palabras clave (clave, valor): resultado

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 

muestra:

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

Esto parece encajar "Algorithms using finite set of patterns"

El algoritmo Aho–Corasick string matching es una búsqueda de cadenas algoritmo inventado por Alfred V. Aho y Margaret J. Corasick. Es un tipo del algoritmo de búsqueda de diccionario que localiza elementos de un conjunto finito de cadenas (el "diccionario") dentro de un texto de entrada . Coincide con todos los patrones "a la vez", por lo que la complejidad del algoritmo es lineal en la longitud de los patrones más la longitud del texto buscado más el número de coincidencias de salida . Tenga en cuenta que debido a que todos se encuentran coincidencias, no puede haber un número de partidos cuadrática si cada subcadena partidos (por ejemplo, el diccionario = A, AA, AAA, AAAA y cadena de entrada es AAAA).

El Rabin–Karp algorithm es un algoritmo de búsqueda de cadena creado por Michael O. Rabin y Richard M. Karp en 1987 que utiliza hash para encontrar uno cualquiera de un conjunto de cadenas de patrones en un texto. Para texto de longitud n y p patrones de longitud combinada m, su promedio y mejor de los casos tiempo de ejecución es O (n + m) en espacio O (p), pero su tiempo del peor caso es O (nm) . Por el contrario, el algoritmo de coincidencia de cadenas Aho-Corasick tiene complejidad asintótica del peor momento O (n + m) en el espacio O (m).

Answer 2

puedo sugerir a los enfoques:

1) Tokenise usando string.Split y partido contra un diccionario de teclas que debe

2) Implementar tokenizador usted mismo un lector con ReadToken() método que se añade a los personajes a una búfer hasta que encuentre (Split podría estar haciendo eso) un carácter dividido y lo emite como token. Luego revisas tu diccionario.

Answer 3

Tal vez sea un poco exagerado, pero definitivamente debe echar un vistazo a ANTLR.

Answer 4

Si usted tiene un conjunto fijo de palabras clave que puede utilizar (f) lex, re2c o ragel

Answer 5

me gustaría utilizar expresiones regulares precompilados para cada grupo de palabras clave para que coincidan. En el fondo, estos están "compilados" para autómatas finitos, por lo que son bastante rápidos en el reconocimiento del patrón en su cadena y mucho más rápido que un Contains para cada una de las posibles cadenas.

usando: System.Text.RegularExpressions.

En su ejemplo:

• "Schw", "schwa". y "Schwarz"
• new Regex(@"schw(a?\.|arz)", RegexOptions.Compiled)

más documentación disponible aquí: http://msdn.microsoft.com/en-us/library/system.text.regularexpressions.regexoptions(v=VS.90).aspx