一尘不染

相似的字符串算法

algorithm

我正在寻找一种算法,或者至少是关于如何在两个或多个不同字符串中找到相似文本的操作理论…

就像这里提出的问题一样:查找具有相似文本的文章的算法,不同之处在于我的文本字符串只会是少数几个单词。

就像说我有一个字符串:“进入湛蓝的天空”,我正在与以下两个字符串进行比较:“颜色是天蓝色”和“在湛蓝的天空中”

我正在寻找一种可用于匹配两个文本的算法,并确定它们之间的匹配程度。就我而言,拼写和标点符号将很重要。我不希望他们影响发现真实文本的能力。在上面的示例中,如果颜色参考存储为“’天蓝色’”,我希望它仍然能够匹配。但是,列出的第三个字符串应该比第二个更好,依此类推。

我敢肯定,像Google这样的地方可能会使用与“您的意思是:”功能类似的东西…

编辑
在与朋友交谈时,他与一个就此主题撰写论文的人一起工作。我想与所有阅读此书的人分享一下,因为其中描述了一些非常好的方法和过程…

这是他论文链接,希望对阅读此问题的人以及类似字符串算法的主题有所帮助。


阅读 213

收藏
2020-07-28

共1个答案

一尘不染

我无法在此处标记两个答案,因此我将回答并标记自己的答案。在大多数情况下,Levenshtein距离似乎是正确的方法。但是,值得一提j_random_hackers也回答。我已经使用LZMA的实现来测试他的理论,事实证明这是一个合理的解决方案。在我最初的问题中,我正在寻找一种用于短字符串(2至200个字符)的方法,Levenshtein距离算法将在此方法中起作用。但是,问题中没有提到需要比较两个(较大的)字符串(在这种情况下,是中等大小的文本文件)并进行快速检查以查看两者的相似程度。我相信这种压缩技术会很好用,但是我还没有研究它,就样本数据的大小和所讨论操作的速度/成本而言,发现哪一种优于另一种。对于想解决类似字符串折磨的任何人,我想在此问题上给出的许多答案都是有价值的,并且值得一提。

2020-07-28