search

hfuuss / algorithm-JS

ACM算法总结 总结在Issues里面
1 stars 0 forks source link

33|字符串匹配基础(中):如何实现文本编辑器中的查找功能? #30

Open hfuuss opened 5 years ago

hfuuss commented 5 years ago

对于工业级的软件开发来说，我们希望算法尽可能的高效，并且在极端情况下，性能也不要退化的太严重。那么，对于查找功能是重要功能的软件来说，比如一 些文本编辑器，它们的查找功能都是用哪种算法来实现的呢?有没有比BF算法和RK算法更加高效的字符串匹配算法呢? 今天，我们就来学习BM(Boyer-Moore)算法。它是一种非常高效的字符串匹配算法，有实验统计，它的性能是著名的KMP算法的3到4倍。BM算法的原理很复 杂，比较难懂，学起来会比较烧脑，我会尽量给你讲清楚，同时也希望你做好打硬仗的准备。好，现在我们正式开始!

hfuuss commented 5 years ago

今天，我们讲了一种比较复杂的字符串匹配算法，BM算法。尽管复杂、难懂，但匹配的效率却很高，在实际的软件开发中，特别是一些文本编辑器中，应用比较 多。如果一遍看不懂的话，你就多看几遍。 BM算法核心思想是，利用模式串本身的特点，在模式串中某个字符与主串不能匹配的时候，将模式串往后多滑动几位，以此来减少不必要的字符比较，提高匹配 的效率。BM算法构建的规则有两类，坏字符规则和好后缀规则。好后缀规则可以独立于坏字符规则使用。因为坏字符规则的实现比较耗内存，为了节省内存，我 们可以只用好后缀规则来实现BM算法。