我需要一种方法来比较多个字符串到一个测试字符串，并返回与它非常相似的字符串:
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。此时，伪代码是可以接受的。如果你能提供一个特定语言的例子，这也是非常感谢的!
当前回答
如果您在搜索引擎上下文中执行此操作，或者在数据库前端执行此操作，则可以考虑使用类似Apache Solr的工具，并使用ComplexPhraseQueryParser插件。这种组合允许您搜索字符串索引，并根据相关性(由Levenshtein距离确定)对结果进行排序。
当传入的查询可能有一个或多个拼写错误时，我们一直在对大量艺术家和歌曲标题的集合使用它，并且它工作得非常好(考虑到集合包含数百万个字符串，它的速度非常快)。
此外，使用Solr，您可以根据需要通过JSON根据索引进行搜索，因此不必在不同的语言之间重新设计解决方案。
其他回答
如果您在搜索引擎上下文中执行此操作，或者在数据库前端执行此操作，则可以考虑使用类似Apache Solr的工具，并使用ComplexPhraseQueryParser插件。这种组合允许您搜索字符串索引，并根据相关性(由Levenshtein距离确定)对结果进行排序。
当传入的查询可能有一个或多个拼写错误时，我们一直在对大量艺术家和歌曲标题的集合使用它，并且它工作得非常好(考虑到集合包含数百万个字符串，它的速度非常快)。
此外，使用Solr，您可以根据需要通过JSON根据索引进行搜索，因此不必在不同的语言之间重新设计解决方案。
我怀疑选项B更接近测试字符串，因为它距离原始字符串只有4个字符(和2个删除)。而C更接近，因为它同时包含棕色和红色。但是，它有一个更大的编辑距离。
有一种叫做Levenshtein Distance的算法可以测量两个输入之间的编辑距离。
这里有一个算法工具。
选择A的距离是15。 选择B的距离是6。 选择C的距离为9。
编辑:对不起，我一直在levenshtein工具混合字符串。更新到正确的答案。
这里你可以有一个golang POC来计算给定单词之间的距离。您可以为其他作用域调整minDistance和difference。
操场上:https://play.golang.org/p/NtrBzLdC3rE
package main
import (
"errors"
"fmt"
"log"
"math"
"strings"
)
var data string = `THE RED COW JUMPED OVER THE GREEN CHICKEN-THE RED COW JUMPED OVER THE RED COW-THE RED FOX JUMPED OVER THE BROWN COW`
const minDistance float64 = 2
const difference float64 = 1
type word struct {
data string
letters map[rune]int
}
type words struct {
words []word
}
// Print prettify the data present in word
func (w word) Print() {
var (
lenght int
c int
i int
key rune
)
fmt.Printf("Data: %s\n", w.data)
lenght = len(w.letters) - 1
c = 0
for key, i = range w.letters {
fmt.Printf("%s:%d", string(key), i)
if c != lenght {
fmt.Printf(" | ")
}
c++
}
fmt.Printf("\n")
}
func (ws words) fuzzySearch(data string) ([]word, error) {
var (
w word
err error
founds []word
)
w, err = initWord(data)
if err != nil {
log.Printf("Errors: %s\n", err.Error())
return nil, err
}
// Iterating all the words
for i := range ws.words {
letters := ws.words[i].letters
//
var similar float64 = 0
// Iterating the letters of the input data
for key := range w.letters {
if val, ok := letters[key]; ok {
if math.Abs(float64(val-w.letters[key])) <= minDistance {
similar += float64(val)
}
}
}
lenSimilarity := math.Abs(similar - float64(len(data)-strings.Count(data, " ")))
log.Printf("Comparing %s with %s i've found %f similar letter, with weight %f", data, ws.words[i].data, similar, lenSimilarity)
if lenSimilarity <= difference {
founds = append(founds, ws.words[i])
}
}
if len(founds) == 0 {
return nil, errors.New("no similar found for data: " + data)
}
return founds, nil
}
func initWords(data []string) []word {
var (
err error
words []word
word word
)
for i := range data {
word, err = initWord(data[i])
if err != nil {
log.Printf("Error in index [%d] for data: %s", i, data[i])
} else {
words = append(words, word)
}
}
return words
}
func initWord(data string) (word, error) {
var word word
word.data = data
word.letters = make(map[rune]int)
for _, r := range data {
if r != 32 { // avoid to save the whitespace
word.letters[r]++
}
}
return word, nil
}
func main() {
var ws words
words := initWords(strings.Split(data, "-"))
for i := range words {
words[i].Print()
}
ws.words = words
solution, _ := ws.fuzzySearch("THE BROWN FOX JUMPED OVER THE RED COW")
fmt.Println("Possible solutions: ", solution)
}
你可能会对这篇博客感兴趣。
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/
如果输入数据太大(比如数百万个字符串)，这个问题就很难实现。我用弹性搜索来解决这个问题。
快速入门: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))
)
));
