Livres sur des algorithmes de string

CLR possède des algorithmes de traitement de chaîne, mais ce n'est pas spécifique à eux.

y compris:

• Knuth-Morris-Pratt
• Rabin-Karp
• correspondant par Automate fini
• Distance d'édition

Tre est une bibliothèque open source qui implémente une correspondance approximative. à propos de la page a des conseils intéressants sur la façon dont cela fonctionne, bien que je ne suis pas sûr qu'il fournisse la Sorte d'analyse en profondeur que vous recherchez. Le code source est probablement plus éclairant de cette perspective.

Ce n'est pas une recommandation de livre, mais cette bibliothèque et cette bibliothèque sont une bibliothèque qui offre de nombreuses implémentations d'algorithme correspondantes à chaîne efficaces:

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

Il fournit également des liens vers l'apprentissage ultérieur pour chacun et où chacun est le mieux applicable.

Je suis surpris que personne ait mentionné l'excellent livre d'excellent Dan Gusfield Algorithmes sur les cordes, les arbres et les séquences qui couvre des algorithmes de cordes plus en détail que quiconque aurait probablement besoin. Cela m'a très bien servi pour un projet sur le séquençage des protéines que je travaillais il y a quelques années. Après avoir lu ce livre, vous apprendrez:

• String naïf correspondant
• Algorithmes à base de préprocesseur (Boyer Moore, Knuth-Morris-Pratt)
• Algorithmes correspondants Regex
• karp-rabin et méthodes similaires
• Les méthodes d'arbre suffixe (méthode de Ukkonen, etc.)
• Alignement de la séquence (distance de la distance et de chaîne de Levenshtein et alignement de la séquence multiple)
• Applications aux séquençages de l'ADN, prédiction de gènes et autres zones.

bijoux de stringologie