相关疑难解决方法(0)

我正在寻找一个可以进行简单的模糊字符串比较的 Python 模块。具体来说，我想要字符串相似程度的百分比。我知道这可能是主观的，所以我希望找到一个可以进行位置比较以及最长相似字符串匹配等的库。

基本上，我希望找到足够简单的东西来产生单个百分比，同时仍然足够可配置，以便我可以指定要进行的比较类型。

我在数据库中有很多文章(标题,文字),我正在寻找一种算法来找到X最相似的文章,比如Stack Overflow的"相关问题",当你提出问题时.

我尝试谷歌搜索,但只找到关于其他"类似文本"问题的页面,比如将每篇文章与所有其他文章进行比较并在某处存储相似性.因此,我只是在我刚输入的文本上"实时"执行此操作.

怎么样？

我需要比较2个字符串并计算它们的相似性,以过滤掉最相似字符串的列表.

例如.寻找"狗"会回来

1. 狗
2. 该死
3. 沼泽
4. 多雾路段
5. 有雾

例如.寻找"破解"将返回

1. 裂纹
2. 俏皮话
3. 架
4. 插口
5. 嘎嘎

我遇到过:

• 水银
• 的Liquidmetal

你知道更多的字符串相似度算法吗？

我把"chunk transposition"放在引号中,因为我不知道技术术语应该是什么或者是什么.只知道该过程是否有技术术语将非常有帮助.

关于编辑距离的维基百科文章给出了一些关于这个概念的好背景.

通过考虑"块转置",我的意思是

Turing, Alan.

应该匹配

Alan Turing

比它更匹配

Turing Machine

即距离计算应检测文本的子串何时在文本中移动.常见的Levenshtein距离公式不是这种情况.

字符串最多只有几百个字符 - 它们是作者姓名或作者姓名列表,可以是各种格式.我没有做DNA测序(虽然我怀疑那些会对这个主题有所了解的人).

我需要实现某种形式:

string textToSearch = "Extreme Golf: The Showdown";
string textToSearchFor = "Golf Extreme Showdown";
int fuzzyMatchScoreThreshold = 80; // One a 0 to 100 scale
bool searchSuccessful = IsFuzzyMatch(textToSearch, textToSearchFor, fuzzyMatchScoreThreshold);
if (searchSuccessful == true)
{
    -- we have a match.
}

这是用C#编写的函数存根:

public bool IsFuzzyMatch (string textToSearch, string textToSearchFor, int fuzzyMatchScoreThreshold)
{
   bool isMatch = false;
   // do fuzzy logic here and set isMatch to true if successful match.
   return isMatch;
}

但我不知道如何在IsFuzzyMatch方法中实现逻辑.有任何想法吗？也许为此目的有一个现成的解决方案？

字符串算法上有很多帖子:

• 查找具有相似文本的文章的算法,
• 类似String算法,
• 高效的字符串匹配算法

但是,没有提到一般文献.

任何人都可以推荐一本能彻底探索各种字符串算法的书吗？特别感兴趣的主题是近似字符串匹配[像谷歌提供的纠正搜索字符串变体:)].

非常感谢您的建议.

Levenshtein距离为我们提供了一种根据无序个体字符计算两个相似字符串之间距离的方法:

quick brown fox
quikc brown fax

Levenshtein距离= 3.

具有相似子序列的两个字符串之间距离的类似算法是什么？例如,在

quickbrownfox
brownquickfox

Levenshtein距离是10,但这并没有考虑到弦有两个相似的子序列的事实,这使得它们比完全无序的词更像"相似"

quickbrownfox
qburiocwknfox

然而,这个完全无序的版本的Levenshtein距离为8.

考虑到子序列的长度,存在哪些距离度量,而不假设子序列可以很容易地分成不同的词？