获取最接近的字符串匹配

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

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。此时，伪代码是可以接受的。如果你能提供一个特定语言的例子，这也是非常感谢的!

当前回答

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

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;
}

结果:

2022-11-03 03:56:18

其他回答

这个问题在生物信息学中经常出现。上面被接受的答案(顺便说一下，它很棒)在生物信息学中被称为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亿个字母长。自然，我们会想要对数据进行成对的不精确字符串匹配…

2012-05-04 08:07:22

要以有效的方式查询大量文本，可以使用编辑距离/前缀编辑距离的概念。

编辑距离ED(x,y):从项x到项y的最小变换数

但是计算每个术语和查询文本之间的ED是资源和时间密集型的。因此，我们可以使用一种称为Qgram Index的技术提取可能匹配的项，而不是首先计算每个项的ED。然后对这些选定的项进行ED计算。

Qgram索引技术的优点是支持模糊搜索。

采用QGram索引的一种可能的方法是使用QGram构建倒排索引。在那里，我们存储了所有与特定Qgram组成的单词，在那个Qgram之下。(而不是存储完整的字符串，您可以为每个字符串使用唯一的ID)。为此，您可以使用Java中的Tree Map数据结构。下面是存储术语的一个小示例

科尔姆比亚，科伦坡，甘科拉，塔科拉马

然后，在查询时，我们计算查询文本和可用术语之间的公共Qgrams的数量。

Example: x = HILLARY, y = HILARI(query term)
Qgrams
$$HILLARY$$ -> $$H, $HI, HIL, ILL, LLA, LAR, ARY, RY$, Y$$
$$HILARI$$ -> $$H, $HI, HIL, ILA, LAR, ARI, RI$, I$$
number of q-grams in common = 4

共有q-gram数= 4。

对于具有大量常见Qgrams的术语，我们根据查询术语计算ED/PED，然后向最终用户建议该术语。

你可以在下面的项目中找到这个理论的实现(参见“QGramIndex.java”)。请随意提问。https://github.com/Bhashitha-Gamage/City_Search

要了解更多关于编辑距离，前缀编辑距离Qgram索引，请观看Hannah Bast教授的视频https://www.youtube.com/embed/6pUg2wmGJRo(课程从20:06开始)

2017-04-03 06:30:02

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

}

2020-02-09 20:32:24

还有一个相似度测量，我曾经在我们的系统中实施，并给出了令人满意的结果:-

用例

有一个用户查询需要与一组文档进行匹配。

算法

从用户查询中提取关键字(相关POS TAGS -名词，专有名词)。现在根据下面的公式计算分数，用于测量用户查询和给定文档之间的相似性。

对于从用户查询中提取的每个关键字:-

开始在文档中搜索给定的单词，并在文档中每出现一次该单词就减少奖励点数。

从本质上讲，如果第一个关键字在文档中出现了4次，则得分将计算为:-

第一次出现将获取'1'点。第二次出现将在计算分数上加1/2 第三次会增加总数的1/3 第四次得到1/4

总相似度= 1 + 1/2 + 1/3 + 1/4 = 2.083

类似地，我们为用户查询中的其他关键字计算它。