获取最接近的字符串匹配

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

有一个叫做Levenshtein距离的算法，它测量两个输入之间的编辑距离。

在这里是该算法的一个工具。

1. 选择A的距离是15。
2. 选择B的距离是6。
3. 选择C的距离为9。

编辑:对不起，我一直在levenshtein工具混合字符串。更新到正确的答案。

大约一年前，我遇到了这个问题，当时我要在一个杂项信息数据库中查找用户输入的关于石油钻井平台的信息。目标是执行某种模糊字符串搜索，以识别具有最常见元素的数据库条目。

部分研究涉及实现Levenshtein距离算法，该算法确定必须对字符串或短语进行多少更改才能将其转换为另一个字符串或短语。

我提出的实现相对简单，涉及两个短语的长度、每个短语之间的变化数量以及是否可以在目标条目中找到每个单词的加权比较。

这篇文章在一个私人网站上，所以我会尽我所能在这里附上相关内容:

模糊字符串匹配是对两个单词或短语的相似度进行类似人类估计的过程。在许多情况下，它包括识别彼此最相似的单词或短语。本文描述了模糊字符串匹配问题的内部解决方案，以及它在解决各种问题方面的有用性，这些问题可以使我们将以前需要冗长的用户参与的任务自动化。

简介

在开发墨西哥湾Validator工具时，需要进行模糊字符串匹配。现有的是一个已知的墨西哥湾石油钻井平台的数据库，购买保险的人会给我们一些关于他们资产的糟糕输入信息，我们必须将其与已知平台的数据库进行匹配。当提供的信息很少时，我们能做的最好的事情就是依靠承销商“识别”他们所指的并调出适当的信息。这就是自动化解决方案派上用场的地方。

我花了一天的时间研究模糊字符串匹配的方法，最终在维基百科上偶然发现了非常有用的Levenshtein距离算法。

实现

在阅读了它背后的理论之后，我实现了它，并找到了优化它的方法。这是我的代码在VBA中的样子:

'Calculate the Levenshtein Distance between two strings (the number of insertions,
'deletions, and substitutions needed to transform the first string into the second)
Public Function LevenshteinDistance(ByRef S1 As String, ByVal S2 As String) As Long
Dim L1 As Long, L2 As Long, D() As Long 'Length of input strings and distance matrix
Dim i As Long, j As Long, cost As Long 'loop counters and cost of substitution for current letter
Dim cI As Long, cD As Long, cS As Long 'cost of next Insertion, Deletion and Substitution
L1 = Len(S1): L2 = Len(S2)
ReDim D(0 To L1, 0 To L2)
For i = 0 To L1: D(i, 0) = i: Next i
For j = 0 To L2: D(0, j) = j: Next j


For j = 1 To L2
For i = 1 To L1
cost = Abs(StrComp(Mid$(S1, i, 1), Mid$(S2, j, 1), vbTextCompare))
cI = D(i - 1, j) + 1
cD = D(i, j - 1) + 1
cS = D(i - 1, j - 1) + cost
If cI <= cD Then 'Insertion or Substitution
If cI <= cS Then D(i, j) = cI Else D(i, j) = cS
Else 'Deletion or Substitution
If cD <= cS Then D(i, j) = cD Else D(i, j) = cS
End If
Next i
Next j
LevenshteinDistance = D(L1, L2)
End Function

简单，快速，非常有用的度量标准。使用这个，我创建了两个单独的度量来评估两个字符串的相似性。一个叫valuePhrase，一个叫valueWords。valuePhrase只是两个短语之间的Levenshtein距离，valueWords根据空格、破号和其他任何你想要的分隔符将字符串分割成单独的单词，并将每个单词与其他单词进行比较，总结连接任何两个单词的最短Levenshtein距离。从本质上讲，它衡量的是一个“短语”中的信息是否真的包含在另一个“短语”中，就像一个单词的排列一样。我花了几天的时间作为一个副业，想出了基于分隔符分割字符串的最有效的方法。

valueWords, valuePhrase和Split函数:

Public Function valuePhrase#(ByRef S1$, ByRef S2$)
valuePhrase = LevenshteinDistance(S1, S2)
End Function


Public Function valueWords#(ByRef S1$, ByRef S2$)
Dim wordsS1$(), wordsS2$()
wordsS1 = SplitMultiDelims(S1, " _-")
wordsS2 = SplitMultiDelims(S2, " _-")
Dim word1%, word2%, thisD#, wordbest#
Dim wordsTotal#
For word1 = LBound(wordsS1) To UBound(wordsS1)
wordbest = Len(S2)
For word2 = LBound(wordsS2) To UBound(wordsS2)
thisD = LevenshteinDistance(wordsS1(word1), wordsS2(word2))
If thisD < wordbest Then wordbest = thisD
If thisD = 0 Then GoTo foundbest
Next word2
foundbest:
wordsTotal = wordsTotal + wordbest
Next word1
valueWords = wordsTotal
End Function


''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
' SplitMultiDelims
' This function splits Text into an array of substrings, each substring
' delimited by any character in DelimChars. Only a single character
' may be a delimiter between two substrings, but DelimChars may
' contain any number of delimiter characters. It returns a single element
' array containing all of text if DelimChars is empty, or a 1 or greater
' element array if the Text is successfully split into substrings.
' If IgnoreConsecutiveDelimiters is true, empty array elements will not occur.
' If Limit greater than 0, the function will only split Text into 'Limit'
' array elements or less. The last element will contain the rest of Text.
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
Function SplitMultiDelims(ByRef Text As String, ByRef DelimChars As String, _
Optional ByVal IgnoreConsecutiveDelimiters As Boolean = False, _
Optional ByVal Limit As Long = -1) As String()
Dim ElemStart As Long, N As Long, M As Long, Elements As Long
Dim lDelims As Long, lText As Long
Dim Arr() As String


lText = Len(Text)
lDelims = Len(DelimChars)
If lDelims = 0 Or lText = 0 Or Limit = 1 Then
ReDim Arr(0 To 0)
Arr(0) = Text
SplitMultiDelims = Arr
Exit Function
End If
ReDim Arr(0 To IIf(Limit = -1, lText - 1, Limit))


Elements = 0: ElemStart = 1
For N = 1 To lText
If InStr(DelimChars, Mid(Text, N, 1)) Then
Arr(Elements) = Mid(Text, ElemStart, N - ElemStart)
If IgnoreConsecutiveDelimiters Then
If Len(Arr(Elements)) > 0 Then Elements = Elements + 1
Else
Elements = Elements + 1
End If
ElemStart = N + 1
If Elements + 1 = Limit Then Exit For
End If
Next N
'Get the last token terminated by the end of the string into the array
If ElemStart <= lText Then Arr(Elements) = Mid(Text, ElemStart)
'Since the end of string counts as the terminating delimiter, if the last character
'was also a delimiter, we treat the two as consecutive, and so ignore the last elemnent
If IgnoreConsecutiveDelimiters Then If Len(Arr(Elements)) = 0 Then Elements = Elements - 1


ReDim Preserve Arr(0 To Elements) 'Chop off unused array elements
SplitMultiDelims = Arr
End Function

相似度度量

使用这两个指标，以及简单计算两个字符串之间距离的第三个指标，我有一系列变量，我可以运行优化算法来实现最大数量的匹配。模糊字符串匹配本身是一门模糊科学，因此通过创建线性无关的度量标准来测量字符串的相似性，并拥有一组我们希望彼此匹配的已知字符串，我们可以找到对于特定类型的字符串，给出最佳模糊匹配结果的参数。

最初，度量的目标是为精确匹配提供一个低搜索值，并为不断排列的度量增加搜索值。在不实际的情况下，使用一组定义良好的排列来定义这是相当容易的，并设计最终公式，使它们具有所需的增加搜索值的结果。

在上面的截图中，我调整了我的启发式，想出了一些我觉得很好地缩放到我感知到的搜索词和结果之间的差异的东西。我在上面的电子表格中用于Value Phrase的启发式是=valuePhrase(A2,B2)-0.8*ABS(LEN(B2)-LEN(A2))。我有效地将Levenstein距离的惩罚减少了两个“短语”长度差异的80%。这样，具有相同长度的“短语”将受到全部惩罚，但包含“额外信息”(更长)但除此之外大部分字符仍然相同的“短语”将受到较少的惩罚。我按原样使用Value Words函数，然后我的最终SearchVal启发式被定义为=MIN(D2,E2)*0.8+MAX(D2,E2)*0.2 -一个加权平均值。两个分数中哪个较低的权重为80%，哪个较高的权重为20%。这只是适合我的用例以获得良好匹配率的启发式方法。这些权重可以通过调整来获得与测试数据的最佳匹配率。

.

正如您所看到的，最后两个指标是模糊字符串匹配指标，已经有一种自然的倾向，即对打算匹配的字符串给予低分(对角线向下)。这很好。

<强>应用程序 为了优化模糊匹配，我对每个指标进行了加权。因此，模糊字符串匹配的每种应用都可以对不同的参数进行不同的加权。定义最终分数的公式是指标及其权重的简单组合:

value = Min(phraseWeight*phraseValue, wordsWeight*wordsValue)*minWeight
+ Max(phraseWeight*phraseValue, wordsWeight*wordsValue)*maxWeight
+ lengthWeight*lengthValue

使用优化算法(神经网络在这里是最好的，因为它是一个离散的、多维的问题)，现在的目标是最大化匹配的数量。我创建了一个函数来检测每个集合之间正确匹配的数量，如最后一个截图所示。如果将最低的分数分配给要匹配的字符串，则列或行获得一分，如果最低的分数相同，并且正确的匹配是在已匹配的字符串中，则给予部分分。然后我优化了它。可以看到，绿色单元格是与当前行最匹配的列，单元格周围的蓝色方框是与当前列最匹配的行。底部角落的分数大致是成功匹配的数量，这是我们告诉优化问题最大化的值。

这个算法非常成功，解的参数说明了很多关于这类问题的信息。您将注意到优化的分数是44，而最好的分数是48。最后的5列是假的，与行值没有任何匹配。诱饵越多，自然就越难找到最佳匹配。

在这种特殊的匹配情况下，字符串的长度是不相关的，因为我们期望表示较长的单词的缩写，因此长度的最佳权重是-0.3，这意味着我们不会惩罚长度变化的字符串。我们降低了对这些缩写的预期得分，为部分单词匹配提供了更多的空间，以取代非单词匹配，因为字符串更短，只需要更少的替换。

单词的权重是1.0，而短语的权重只有0.5，这意味着我们会惩罚一个字符串中缺失的整个单词，而更重视整个短语的完整。这很有用，因为很多字符串都有一个共同的单词(危险)，真正重要的是是否保持组合(区域和危险)。

最后，最小权重优化为10，最大权重优化为1。这意味着，如果两个分数中最好的分数(价值短语和价值词)不是很好，比赛将受到很大的惩罚，但我们不会对两个分数中最差的分数进行很大的惩罚。本质上，这强调要求要么 valueWord或valuePhrase具有良好的分数，而不是两者都有。一种“能得到什么就拿什么”的心态。

这5个权重的优化值说明了发生的模糊字符串匹配，这真的很有趣。对于完全不同的模糊字符串匹配的实际情况，这些参数是非常不同的。到目前为止，我已经在3个不同的应用程序中使用了它。

虽然在最终优化中未使用，但建立了一个基准表，它将列与自己相匹配，以获得对角线上的所有完美结果，并让用户改变参数来控制得分从0偏离的比率，并注意搜索短语之间的固有相似性(理论上可以用于抵消结果中的假阳性)

进一步的应用

这种解决方案有潜力用于任何用户希望计算机系统识别一组字符串中没有完美匹配的字符串的地方。(类似于字符串的近似匹配vlookup)。

因此，您应该从中得到的是，您可能想要使用高级启发式的组合(从一个短语中找到另一个短语中的单词，两个短语的长度，等等)以及Levenshtein距离算法的实现。因为决定哪个是“最佳”匹配是一种启发式(模糊)决定——你必须为你想到的任何指标提出一组权重来确定相似性。

有了合适的启发式和权重集，比较程序就能快速做出你本应做出的决定。

Lua实现，为子孙后代:

function levenshtein_distance(str1, str2)
local len1, len2 = #str1, #str2
local char1, char2, distance = {}, {}, {}
str1:gsub('.', function (c) table.insert(char1, c) end)
str2:gsub('.', function (c) table.insert(char2, c) end)
for i = 0, len1 do distance[i] = {} end
for i = 0, len1 do distance[i][0] = i end
for i = 0, len2 do distance[0][i] = i end
for i = 1, len1 do
for j = 1, len2 do
distance[i][j] = math.min(
distance[i-1][j  ] + 1,
distance[i  ][j-1] + 1,
distance[i-1][j-1] + (char1[i] == char2[j] and 0 or 1)
)
end
end
return distance[len1][len2]
end

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

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/

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

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

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

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

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

有很多非常好的算法可以进行精确的字符串匹配。给定一个长度为200的查询字符串和一个长度为30亿的目标字符串(人类基因组)，我们希望在目标中找到长度为k的子字符串与查询的子字符串完全匹配的任何位置。一种简单的方法是首先对目标进行索引:获取所有k长的子字符串，将它们放在一个数组中并对它们进行排序。然后获取查询的每个k长子字符串并搜索已排序的索引。排序和搜索可以在O(log n)时间内完成。

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

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

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

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

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

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

瞧(由“Wayback Machine”提供):http://web.archive.org/web/20081230184321/http://www.dcs.shef.ac.uk/~sam/simmetrics.html

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

如果你在搜索引擎的上下文中做这个，或者在数据库的前端做这个，你可以考虑使用像Apache Solr这样的工具，带有ComplexPhraseQueryParser插件。这种组合允许您搜索字符串索引，并根据相关性(由Levenshtein距离确定)对结果进行排序。

当传入的查询可能有一个或多个拼写错误时，我们一直在对大量艺术家和歌曲标题的集合使用它，并且它工作得非常好(考虑到集合包含数百万个字符串，它的速度非常快)。

此外，使用Solr，您可以根据需要通过JSON根据索引进行搜索，因此不必在不同的语言之间重新设计解决方案。

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

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

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

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

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

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

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

col: 上校mbia， 上校ombo, gan上校a, ta上校ama

然后，在查询时，我们计算查询文本和可用术语之间的公共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开始)

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

快速入门: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)


}

一个使用c#在这里的示例。

public static void Main()
{
Console.WriteLine("Hello World " + LevenshteinDistance("Hello","World"));
Console.WriteLine("Choice A " + LevenshteinDistance("THE BROWN FOX JUMPED OVER THE RED COW","THE RED COW JUMPED OVER THE GREEN CHICKEN"));
Console.WriteLine("Choice B " + LevenshteinDistance("THE BROWN FOX JUMPED OVER THE RED COW","THE RED COW JUMPED OVER THE RED COW"));
Console.WriteLine("Choice C " + LevenshteinDistance("THE BROWN FOX JUMPED OVER THE RED COW","THE RED FOX JUMPED OVER THE BROWN COW"));
}


public static float LevenshteinDistance(string a, string b)
{
var rowLen = a.Length;
var colLen = b.Length;
var maxLen = Math.Max(rowLen, colLen);


// Step 1
if (rowLen == 0 || colLen == 0)
{
return maxLen;
}


/// Create the two vectors
var v0 = new int[rowLen + 1];
var v1 = new int[rowLen + 1];


/// Step 2
/// Initialize the first vector
for (var i = 1; i <= rowLen; i++)
{
v0[i] = i;
}


// Step 3
/// For each column
for (var j = 1; j <= colLen; j++)
{
/// Set the 0'th element to the column number
v1[0] = j;


// Step 4
/// For each row
for (var i = 1; i <= rowLen; i++)
{
// Step 5
var cost = (a[i - 1] == b[j - 1]) ? 0 : 1;


// Step 6
/// Find minimum
v1[i] = Math.Min(v0[i] + 1, Math.Min(v1[i - 1] + 1, v0[i - 1] + cost));
}


/// Swap the vectors
var vTmp = v0;
v0 = v1;
v1 = vTmp;
}


// Step 7
/// The vectors were swapped one last time at the end of the last loop,
/// that is why the result is now in v0 rather than in v1
return v0[rowLen];
}

输出结果为:

Hello World 4
Choice A 15
Choice B 6
Choice C 8

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

用例

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

算法

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

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

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

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

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

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

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

最后，总分将表示用户查询与给定文档之间的相似程度。

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

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

结果: