我需要一种方法来比较多个字符串到一个测试字符串,并返回与它非常相似的字符串:

TEST STRING: THE BROWN FOX JUMPED OVER THE RED COW

CHOICE A   : THE RED COW JUMPED OVER THE GREEN CHICKEN
CHOICE B   : THE RED COW JUMPED OVER THE RED COW
CHOICE C   : THE RED FOX JUMPED OVER THE BROWN COW

(如果我做对了)最接近“TEST string”的字符串应该是“CHOICE C”。最简单的方法是什么?

我计划将其实现为多种语言,包括VB.net、Lua和JavaScript。此时,伪代码是可以接受的。如果你能提供一个特定语言的例子,这也是非常感谢的!


当前回答

这个问题在生物信息学中经常出现。上面被接受的答案(顺便说一下,它很棒)在生物信息学中被称为Needleman-Wunsch(比较两个字符串)和Smith-Waterman(在更长的字符串中找到一个近似的子字符串)算法。它们工作得很好,几十年来一直是主力。

但是如果你有一百万个字符串要比较呢?这是一万亿对的比较,每一个都是O(n*m)!现代DNA测序仪很容易生成10亿个短DNA序列,每个序列大约有200个DNA“字母”长。通常,我们希望为每个这样的字符串找到与人类基因组(30亿个字母)的最佳匹配。显然,Needleman-Wunsch算法及其相关算法是不行的。

这个所谓的“对齐问题”是一个活跃的研究领域。目前最流行的算法能够在合理的硬件(比如8个核和32 GB RAM)上在几个小时内找到10亿个短字符串和人类基因组之间的不精确匹配。

大多数算法的工作原理是快速找到短的精确匹配(种子),然后使用较慢的算法(例如Smith-Waterman)将这些匹配扩展到完整的字符串。这样做的原因是我们真的只对一些接近的比赛感兴趣,所以去掉99.9是值得的…%没有共同之处的配对。

查找精确匹配如何帮助查找不精确匹配?假设我们只允许查询和目标之间有一个差异。很容易看出,这种差异必须出现在查询的右半部分或左半部分,因此另一半必须完全匹配。这种想法可以扩展到多重错配,并且是Illumina DNA测序仪常用的ELAND算法的基础。

There are many very good algorithms for doing exact string matching. Given a query string of length 200, and a target string of length 3 billion (the human genome), we want to find any place in the target where there is a substring of length k that matches a substring of the query exactly. A simple approach is to begin by indexing the target: take all k-long substrings, put them in an array and sort them. Then take each k-long substring of the query and search the sorted index. Sort and search can be done in O(log n) time.

但储存可能是个问题。一个包含30亿个字母目标的索引需要容纳30亿个指针和30亿个k长度的单词。这似乎很难装进小于几十gb的RAM中。但令人惊讶的是,我们可以使用Burrows-Wheeler变换极大地压缩索引,而且它仍然是有效的可查询的。人类基因组的一个索引可以放入不到4 GB的RAM中。这个想法是流行的序列对齐器(如Bowtie和BWA)的基础。

或者,我们可以使用后缀数组,它只存储指针,但表示目标字符串中所有后缀的同时索引(本质上,所有可能的k值的同时索引;Burrows-Wheeler变换也是如此)。如果我们使用32位指针,人类基因组的后缀数组索引将占用12gb RAM。

上面的链接包含了大量的信息和主要研究论文的链接。ELAND链接指向一个PDF,其中有一些有用的图表说明了所涉及的概念,并展示了如何处理插入和删除。

最后,虽然这些算法已经基本解决了(重新)对单个人类基因组(10亿个短字符串)测序的问题,但DNA测序技术的进步甚至比摩尔定律还要快,我们正在快速接近万亿字母的数据集。例如,目前正在进行的项目是对10,000种脊椎动物的基因组进行测序,每个基因组大约有10亿个字母长。自然,我们会想要对数据进行成对的不精确字符串匹配…

其他回答

你可能会发现这个图书馆很有用! http://code.google.com/p/google-diff-match-patch/

目前可以在Java, JavaScript, Dart, c++, c#, Objective C, Lua和Python中使用

它也运行得很好。我在我的几个Lua项目中使用了它。

而且我认为将其移植到其他语言并不困难!

你可能会对这篇博客感兴趣。

http://seatgeek.com/blog/dev/fuzzywuzzy-fuzzy-string-matching-in-python

Fuzzywuzzy是一个Python库,它提供了简单的距离度量,例如用于字符串匹配的Levenshtein距离。它构建在标准库中的difflib之上,并将使用Python-levenshtein(如果可用的话)的C实现。

http://pypi.python.org/pypi/python-Levenshtein/

关于这类算法,一个非常非常好的资源是Simmetrics: http://sourceforge.net/projects/simmetrics/

不幸的是,包含大量文档的很棒的网站已经消失了:( 以防它再次出现,它之前的地址是这样的: http://www.dcs.shef.ac.uk/~sam/simmetrics.html

瞧(由“时光倒流机”提供):http://web.archive.org/web/20081230184321/http://www.dcs.shef.ac.uk/~sam/simmetrics.html

你可以研究一下源代码,有几十种算法可以进行这种比较,每一种都有不同的权衡。这些实现是用Java实现的。

这个问题在生物信息学中经常出现。上面被接受的答案(顺便说一下,它很棒)在生物信息学中被称为Needleman-Wunsch(比较两个字符串)和Smith-Waterman(在更长的字符串中找到一个近似的子字符串)算法。它们工作得很好,几十年来一直是主力。

但是如果你有一百万个字符串要比较呢?这是一万亿对的比较,每一个都是O(n*m)!现代DNA测序仪很容易生成10亿个短DNA序列,每个序列大约有200个DNA“字母”长。通常,我们希望为每个这样的字符串找到与人类基因组(30亿个字母)的最佳匹配。显然,Needleman-Wunsch算法及其相关算法是不行的。

这个所谓的“对齐问题”是一个活跃的研究领域。目前最流行的算法能够在合理的硬件(比如8个核和32 GB RAM)上在几个小时内找到10亿个短字符串和人类基因组之间的不精确匹配。

大多数算法的工作原理是快速找到短的精确匹配(种子),然后使用较慢的算法(例如Smith-Waterman)将这些匹配扩展到完整的字符串。这样做的原因是我们真的只对一些接近的比赛感兴趣,所以去掉99.9是值得的…%没有共同之处的配对。

查找精确匹配如何帮助查找不精确匹配?假设我们只允许查询和目标之间有一个差异。很容易看出,这种差异必须出现在查询的右半部分或左半部分,因此另一半必须完全匹配。这种想法可以扩展到多重错配,并且是Illumina DNA测序仪常用的ELAND算法的基础。

There are many very good algorithms for doing exact string matching. Given a query string of length 200, and a target string of length 3 billion (the human genome), we want to find any place in the target where there is a substring of length k that matches a substring of the query exactly. A simple approach is to begin by indexing the target: take all k-long substrings, put them in an array and sort them. Then take each k-long substring of the query and search the sorted index. Sort and search can be done in O(log n) time.

但储存可能是个问题。一个包含30亿个字母目标的索引需要容纳30亿个指针和30亿个k长度的单词。这似乎很难装进小于几十gb的RAM中。但令人惊讶的是,我们可以使用Burrows-Wheeler变换极大地压缩索引,而且它仍然是有效的可查询的。人类基因组的一个索引可以放入不到4 GB的RAM中。这个想法是流行的序列对齐器(如Bowtie和BWA)的基础。

或者,我们可以使用后缀数组,它只存储指针,但表示目标字符串中所有后缀的同时索引(本质上,所有可能的k值的同时索引;Burrows-Wheeler变换也是如此)。如果我们使用32位指针,人类基因组的后缀数组索引将占用12gb RAM。

上面的链接包含了大量的信息和主要研究论文的链接。ELAND链接指向一个PDF,其中有一些有用的图表说明了所涉及的概念,并展示了如何处理插入和删除。

最后,虽然这些算法已经基本解决了(重新)对单个人类基因组(10亿个短字符串)测序的问题,但DNA测序技术的进步甚至比摩尔定律还要快,我们正在快速接近万亿字母的数据集。例如,目前正在进行的项目是对10,000种脊椎动物的基因组进行测序,每个基因组大约有10亿个字母长。自然,我们会想要对数据进行成对的不精确字符串匹配…

如果输入数据太大(比如数百万个字符串),这个问题就很难实现。我用弹性搜索来解决这个问题。

快速入门:https://www.elastic.co/guide/en/elasticsearch/client/net-api/6.x/elasticsearch-net.html

只需将所有输入数据插入到DB中,您就可以根据任何编辑距离快速搜索任何字符串。下面是一个c#代码片段,它会给你一个按编辑距离排序的结果列表(从小到大)

var res = client.Search<ClassName>(s => s
    .Query(q => q
    .Match(m => m
        .Field(f => f.VariableName)
        .Query("SAMPLE QUERY")
        .Fuzziness(Fuzziness.EditDistance(5))
    )
));