logo标签列表

字符串算法相关书籍推荐

algorithmstring-algorithm
8

关于字符串算法已经有很多帖子：

然而，没有提到任何一般性的文献。

请问有没有推荐的书籍可以全面地探讨各种字符串算法？特别感兴趣的话题是模糊字符串匹配（例如谷歌提供的更正搜索字符串变体）。

非常感谢您的建议。

1
http://en.wikipedia.org/wiki/Levenshtein_distance - Robert Harvey
5个回答
8

我很惊讶没有人提到丹·格斯菲尔德的优秀著作《字符串、树和序列的算法》，该书覆盖了比任何人可能需要的更详细的字符串算法。几年前我在进行蛋白质测序项目时得到了很好的服务。阅读此书后，您将学习：

  • 朴素字符串匹配
  • 基于预处理器的算法（Boyer Moore、Knuth-Morris-Pratt）
  • 正则表达式匹配算法
  • Karp-Rabin和类似方法
  • 后缀树方法（Ukkonen的方法等）
  • 序列对齐（Levenshtein距离和字符串相似性以及多序列对齐）
  • 应用于DNA测序、基因预测和其他领域。
+1 这本书叫做《字符串、树和序列算法》，是一本非常棒的参考书。 - Ian Mercer
而且它是“相对较新的”（与其他答案中提到的文本相比），因为它融合了许多最近的学术作品。 - monn
2
这不是一本书的推荐，而是一个提供大量高效字符串匹配算法实现的图书馆和网站：

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

它还为每个项目提供了进一步学习的链接，并指出最适用的领域。
非常感谢这个。它似乎包含了整个一堆术语和简洁的入门介绍。 - Max
2
1
1

TRE 是一个实现近似匹配的开源库。关于页面 提供了一些有趣的提示，介绍了它的工作原理，但我不确定它是否提供了你所寻找的深入分析。从这个角度来看，源代码可能更具启发性。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接