使用 bitap 算法查找模糊匹配
最近我研究了bitap算法的几种实现，但它们所做的都是找到模糊匹配的起点。我需要的是找到一个匹配。有一个例子：
假设我们有以下文本：abcdefg
和模式：bzde
，我们希望找到文本中模式的所有出现，最多有 1 个错误（考虑编辑距离）。
所以我需要算法返回：bcde。
有没有简单（或不简单=））的方法来做到这一点？ 关于该算法的原始文章没有回答这个问题。
感谢您的帮助。
Reciently I've looked through several implementation of bitap algorithm but what all of them do is finding the beginning point of fuzzy match. What I need is to find a match. There's an example:
Say we have following text: abcdefg
and a pattern: bzde
and we want to find all occurence of a pattern in text with at most 1 error (Edit distance is concidered).
So I need that the algorithm returns: bcde.
Is there a simple (or not simple =) ) way to do it?
The original artical about this algorithm doens't answer the question.
Thank you for your help.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
对于简单的开始，您可以使用一系列正则表达式来处理它，其中在每个表达式中用
.通配符替换 1 个字符。使用( | )构造将这些表达式组合成一个，以创建一个大的正则表达式。另一种方法是扫描字符串，保留错误计数，并在遇到太多错误时增加匹配的偏移量。
For a simple start you could approach it with a series of regular expressions where in every expression you replace 1 character with the
.wildcard. Combining those expressions into one using the( | )construct to create one big regular expression.Another way would be to scan the string keeping an errorcount and incrementing the offset you match at when too many errors are encountered.