Libros en algoritmos de cadena

Question

Ha habido numerosos puestos en los algoritmos de cadena:

• Algorithm to find articles with similar text,
• Similar String algorithm,
• Efficient string matching algorithm

Sin embargo, no se mencionó literatura general.

¿Alguien podría recomendar un libro (s) que exploraría a fondo varios algoritmos de cuerda? El tema que es de especial interés es la coincidencia aproximada de cadenas [cosas como variantes de cadenas de búsqueda corregidas ofrecidas por Google :)].

Muchas gracias por su asesoramiento.

Answer 1

Me sorprende que nadie haya mencionado el excelente libro de Dan Gusfield, Algorithms on Strings, Trees and Sequences, que cubre los algoritmos de cadenas con más detalle de lo que cualquiera probablemente necesitaría. Me fue muy útil para un proyecto sobre secuenciación de proteínas en el que estaba trabajando hace unos años. Después de leer este libro usted aprenderá:

• cadena Naive Coincidencia
• algoritmos preprocesador Basado (Boyer Moore, Knuth-Morris-Pratt)
• Regex algoritmos de correspondencia
• Karp-Rabin y métodos similares
• Métodos del árbol de sufijos (método de Ukkonen, etc.)
• Alineación de secuencias (distancia de Levenshtein y similitud de cadenas y alineación de secuencia múltiple)
• Aplicaciones a secuenciación de ADN, predicción genética y otras áreas.

Answer 2

tiene varios algoritmos de procesamiento de cadenas, pero no es específico para ellos.

Incluyendo:

• Knuth-Morris-Pratt
• Rabin-Karp
• coincidente por autómatas finitos
• distancia de edición

Answer 3

TRE es una biblioteca de código abierto que implementa la correspondencia aproximada. El About page tiene algunos consejos interesantes sobre cómo funciona, aunque no estoy seguro de que proporcione el tipo de análisis en profundidad que está buscando. El código fuente es probablemente más esclarecedor desde esa perspectiva.

Answer 4

Ésta no es una recomendación del libro, pero esta biblioteca y el sitio es una biblioteca que ofrece una gran variedad de implementaciones eficientes algoritmos de coincidencia de cadenas:

http://www.dcs.shef.ac.uk/~sam/simmetrics.html

También proporciona enlaces a un mayor aprendizaje para todos y que cada es mejor aplicable

Answer 5

Jewels of Stringology