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

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/

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

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

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

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

下面是一个不依赖于任何库的快速解决方案，并且可以很好地处理自动完成表单之类的事情:

function compare_strings(str1, str2) {
    arr1 = str1.split("");
    arr2 = str2.split("");
    res = arr1.reduce((a, c) => a + arr2.includes(c), 0);
    return(res)
}

可以像这样在自动完成输入中使用:

HTML:

<div id="wrapper">
    <input id="tag_input" placeholder="add tags..."></input>
    <div id="hold_tags"></div>
</div>

CSS:

body {
  background: #2c2c54;
  display: flex;
  justify-content: center;
  align-items: center;
}

input {
  height: 40px;
  width: 400px;
  border-radius: 4px;
  outline: 0;
  border: none;
  padding-left: 5px;
  font-size: 18px;
}

#wrapper {
  height: auto;
  background: #40407a;
}

.tag {
  background: #ffda79;
  margin: 4px;
  padding: 5px;
  border-radius: 4px;
  box-shadow: 2px 2px 2px black;
  font-size: 18px;
  font-family: arial;
  cursor: pointer;
}

JS:

const input = document.getElementById("tag_input");
const wrapper = document.getElementById("wrapper");
const hold_tags = document.getElementById("hold_tags");
const words = [
  "machine",
  "data",
  "platform",
  "garbage",
  "twitter",
  "knowledge"
];
input.addEventListener("input", function (e) {
  const value = document.getElementById(e.target.id).value;
  hold_tags.replaceChildren();
  if (value !== "") {
    words.forEach(function (word) {
      if (compare_strings(word, value) > value.length - 1) {
        const tag = document.createElement("div");
        tag.className = "tag";
        tag.innerText = word;
        hold_tags.append(tag);
      }
    });
  }
});

function compare_strings(str1, str2) {
  arr1 = str1.split("");
  arr2 = str2.split("");
  res = arr1.reduce((a, c) => a + arr2.includes(c), 0);
  return res;
}

结果:

我怀疑选项B更接近测试字符串，因为它距离原始字符串只有4个字符(和2个删除)。而C更接近，因为它同时包含棕色和红色。但是，它有一个更大的编辑距离。

有一种叫做Levenshtein Distance的算法可以测量两个输入之间的编辑距离。

这里有一个算法工具。

选择A的距离是15。 选择B的距离是6。 选择C的距离为9。

编辑:对不起，我一直在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))
    )
));

这里你可以有一个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)

}