Analizar texto (lematización, distancia de edición)

Question

Necesito analizar el texto para que exista en las palabras prohibidas. Supongamos que la lista negra es la palabra: "Prohibir". La palabra tiene muchas formas. En el texto, la palabra puede ser, por ejemplo: "prohibido", "prohibido", "prohibido". Para llevar la palabra a la forma inicial, utilizo una lematización de proceso. ¿Tus sugerencias?

¿Qué pasa con los errores tipográficos?
Por ejemplo: "F0rb1d". Creo que use damerau-Levenshtein u otro. Usted sugerencias?

¿Y si el texto se escribe como sigue:
"ForbiddenInformation.Privatecorrespondenceofthecompany." O "F0rb1dden1nformation.Privatecorresp0ndenceofthec0mpany". (sí, sin espacio en blanco)

¿Cómo resolver este problema?
Preferiblemente algoritmo rápido, porque el texto se procesa en tiempo real.
Y tal vez, ¿qué algunos consejos para mejorar el rendimiento (cómo almacenar, etc.)?

Lo siento por mi inglés. Gracias.

Answer 1

hay dos soluciones posibles hasta donde sé algoritmos.

Puede intentar utilizar la programación dinámica, LCS (subsecuencia común más larga). Se buscará el texto original de la palabra deseada como patrón, yo creo que es O (mn):

http://en.wikipedia.org/wiki/Longest_common_subsequence_problem http://www.ics.uci.edu/~eppstein/161/960229.html

Aunque el más fácil sería utilizar el algoritmo de búsqueda de texto. Lo mejor que sé es KMP y es O (n). Para la comparación de caracteres, puedes agruparlos en conjuntos como {i I l (L) 1}, {o O 0} y así sucesivamente. Sin embargo, puede modificar esto para que no coincida con todas las letras (prohibir -> forbad).

http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm

Así que ahora se podía comparar los beneficios de estos dos y el suyo sugerencia.

Answer 2

También podría usar RegEx Matches para buscar palabras. http://www.c-sharpcorner.com/uploadfile/prasad_1/regexppsd12062005021717am/regexppsd.aspx