小竞 (编辑)
主要观点：
- 模糊匹配基本上是指当计算机或程序在存在拼写错误、缺失字母、错误拼写等情况下，试图正确确定输入（例如来自人类用户）的意图。
- 模糊匹配一词的使用是因为在考虑计算机通常如何使用严格的逻辑规则处理数据时，“界限变得模糊”。
- 模糊匹配的应用可以在谷歌搜索、shazam等应用程序以及拼写检查中看到。
在我们对需要模糊匹配的原因进行赞美之前，让我们先定义一下模糊匹配，好吗？计算机科学中的模糊匹配技术（有时称为近似字符串匹配）有助于识别两个文本字符串中相似但不完全相同的元素。换句话说，它确定了两个不同字符串之间的接近程度。这个程度是通过计算两个字符串之间的levenshtein距离来确定的。字符串x和y之间的levenshtein距离被定义为将x转换为y所需的最小原始操作数。
模糊匹配就像校对，需要插入、删除和替换字符。
©lamai prasitsuwan/shutterstock.com
下面是三个基本的字符串操作：
- 插入：在字符串的两个其他字符之间插入某个字符，例如从“bot”到“boat”的转变。
- 删除：从字符串中删除某个特定字符，例如从“boat”到“bot”的转变。
- 替换：将字符串中的某个特定字符更改为另一个字符，同时保持字符串的总长度不变，例如从“bot”到“dot”的转变。
形式上，字符串x和y之间的levenshtein距离通过以下递归分段函数定义：
lev(x, y) = {|x| if |y|=0},
{|y| if |x|=0},
{lev(tail(x), tail(y)) if x[0]=y[0]},
还有 {1+min{lev[tail(x),y], lev[tail(y),x], and lev[tail(x), tail(y)]}} otherwise,
其中|x|是x的长度或字符数；tail(x)是通过取x并删除其第一个字符形成的字符串；min(a, b)是a和b之间的最小值；x[n]是字符串x的第n个字符，从0开始计数。因此，x[0]指的是x的第一个字符。
那么，为什么需要模糊匹配？
要回答这个问题，我们必须回溯几步。计算机以准确著称。这种精确性是有用的，使计算机成为我们都知道的极其强大的工具。然而，在某些情况下，它也可能导致没有明确的“是”或“否”的答案-没有我们可以确定的解决方案或给出精确值的解决方案。在这种情况下，有些人会得出结论，认为计算机在获取解决方案方面设备不良或无能。
但是重要的是要考虑到我们多么经常把这类问题委托给计算机处理。如果我们拼错了一个单词，我们会信任拼写检查器 – 这是计算机算法，可以纠正我们的错误并建议正确的单词。当公司发现自己需要将来自不同数据库的同一客户的数据合并时，它们会求助于计算机算法。然而，这些问题是不精确的，许多单词拼写非常相似。有些单词与其他单词押韵，但意义却非常不同（例如，“blew”与“blue”，“through”与“threw”，“there”，“their”或“they're”）。在每个拼写错误的情况下，确定意思并不是一门确切的科学。
同样，如果不同的组织模式将不同的数据库分割开来，那么数据可以被合并的方式可能有无数种。那么，如何编写算法使计算机能够一致地完成这个任务呢？此外，对于基于逻辑门和二进制代码的机器来说，跨不同的人类语言进行翻译并不是一件简单的任务。
尽管如此，计算机确实可以（而且确实）做这样的事情。它们可以进入不确切的领域并提供可靠的解决方案 – 模仿我们所称之为“常识”的东西 – 这不是一个魔术技巧。它最终依靠的是被称为模糊数学或模糊逻辑的东西 – 逻辑或数学的特殊分支，如它们的名称所示，旨在处理模糊和不明确的现象。
因为计算机能够完成在某些情况下看起来不可能的任务，模糊数学的发展产生了广泛而实际的影响。模糊匹配就是其中之一，它值得特别关注，因为它帮助计算机组织和整理不精确的信息。多亏了可以在流行的编程语言（如python和java）中相对容易编写的模糊匹配算法，计算机可以根据字符串之间的接近程度将它们配对。这个简单的技术是每个你听说过的搜索引擎和翻译算法的基础 – 但它的应用远不止于此。
搜索引擎可以使用模糊匹配来确定搜索的意图。
©grisha bruev/shutterstock.com
模糊匹配是如何工作的？
虽然“模糊匹配”的定义可能看起来相当抽象，但它背后的想法相对简单。让我们从一些背景知识开始 – 其中最基础的是模糊数学的概念。
模糊逻辑、数学和集合论
数学和逻辑通常被认为是精确而不灵活的。然而，在过去的50年左右的时间里，许多数学家、哲学家和逻辑学家对模糊性、不准确性、边界情况以及日常语言和生活的混乱性进行了深入的思考。实际上，忽略“模糊性”就是忽视现实的一部分。结果就是模糊数学。
给出一个简单的例子，短语“外面很热”具有真值。然而，不同的人对于他们认为的“热”天气有不同的看法，对于这样的天气的耐受能力也不同等等。因此，短语“外面很热”不能在没有附加限定条件（例如要求的）的情况下明确地被宣称为“真”或“假”。
与经典逻辑不同，模糊逻辑拒绝了被称为双值原理的东西 – 即每个命题p必须是“真”或“假”，并且它们之间不存在中间的真值。模糊逻辑不是唯一一种拒绝这一原则的非经典逻辑形式，但它的特点是为每个命题p赋予无限多的真值之一。
更准确地说，对于每个命题p，模糊逻辑将其分配给闭区间[0, 1]中的某个值，其中值0表示绝对的错误，值1表示绝对的真实性，而每个中间值表示某个真值程度，该程度要么更接近绝对真实性，要么更远离绝对真实性。这使得模糊逻辑能够更加精确地处理像“外面很热”这样的命题。
数学领域，如集合论，也有相应的模糊等价物。在经典集合论中，对象x要么是某个集合s的成员，要么不是。没有“成员等级”的讨论。然而，模糊集合论确实允许在集合中的对象具有成员等级。它通过将模糊集合a定义为从某个全域集x到区间[0, 1]的函数来实现：
a: x → [0,1]
全域集x代表论域，总是被视为经典集合。因此，a(x)的值指的是x在a中的成员程度。将值0映射到x中的某个x意味着x根本不是a的成员，而将值1赋予它意味着它完全在a中。所有中间值都有相应的中间意义。
模糊集合论和模糊逻辑可以通过一个思想来统一，即每个命题都涉及将某个前态指派给一个对象。在经典逻辑中，每个命题都可以表示为x是p，其中x是一个对象，p是某个前态。在经典集合论的语言中解释，这意味着命题x is p变成了x is in the set p，或者x∈p。由于经典逻辑和经典集合论以这种方式相互关联，模糊逻辑和模糊集合论也是相互关联的。
对模糊逻辑或数学的完整讨论将超出本文的范围。然而，这些基本思想重新定义了传统逻辑的概念。由于计算机所做的一切都以逻辑和数学为基础，每个试图解决近似和模糊性（如所有模糊字符串搜索）的算法都必须涉及这个领域。
用于学生培训的传感器、开关和逻辑电路的训练支架，用于说明布尔逻辑。布尔逻辑是一种经典的计算机逻辑形式，模糊匹配有助于解决这个问题。
©istock.com/klmax
levenshtein距离和一些其他算法
下一个需要解决的重要概念是字符串。简单来说，字符串是一系列书写字符。这些字符可以是数字、字母或其他符号。字符串可以是任意长度的。它们可以是与单词对应的序列，例如字符串“hello”，也可以是任何人类语言中的无意义序列，例如“348trhekdsvqdk&%”。
近似字符串匹配是从给定的字符串集合中取一个字符串，并将其与该集合中的另一个字符串匹配，使后者尽可能接近前者的方法。评估“接近度”的操作定义是模糊逻辑概念通常出现的地方。
存在许多不同的模糊字符串搜索算法。有些直接使用模糊概念，作为算法本身的基本架构，而其他一些只在将算法适应特定应用程序时引入模糊概念。
在某种意义上，levenshtein距离函数（如上所定义）并没有直接使用模糊概念，因为它始终提供两个字符串之间距离的准确值。然而，在没有其他字符串与给定字符串x完全相同的情况下，该函数仍然会产生其他字符串作为输出。因此，我们可以认为levenshtein函数是找到一些字符串y的函数，其中语句x is y在模糊逻辑相关意义上是“最真实的” — 即levenshtein函数找到了某个模糊集合y，定义为
y：x → [0,1]
其中，对于给定的x∈x，y(x)≥y(z)， ∀ z∈x。
模糊逻辑概念也可以出现在其他领域。例如，拼写检查算法按照以下基本模式操作。首先，拼写检查器给出一些字符串集合e，这将是像英语这样的语言中所有有效单词的集合。然后，当用户输入一些不在e中的字符串w时（如拼错英语单词），拼写检查器使用levenshtein函数生成一些其他字符串集合c。c是e的子集，其中包含用户可能想要拼写的所有英语单词。通过规定与w的最大允许levenshtein距离，并将满足该条件的所有字符串填充到c中来构建c。这个规定的最大允许距离必须是某种规定的模糊函数的结果 — 这是模糊逻辑与近似字符串匹配相关的另一种方式。
然后，拼写检查器计算p(c)，∀ c∈c，即c中每个可能的候选词在实际使用中出现的概率。拼写检查器可能会使用某种机器学习算法来计算这个概率，因为它了解各种英语单词的使用频率的唯一方法是通过以英语文本的形式输入大量的训练数据。
在此之后，拼写检查器使用某种错误模型来确定用户通过错误拼写的字符串w所指的正确英语单词。错误模型可以简单地声明，与w的levenshtein距离为1的字符串比与w的levenshtein距离为2的字符串更可能是用户的意思，而与w的levenshtein距离为2的字符串更可能是用户的意思，而与w的levenshtein距离为3的字符串更可能是用户的意思，依此类推。然而，在实践中，错误模型几乎肯定比这更复杂，并且将利用实际的英语用法数据。这将再次需要使用某种适当的训练数据来改进的机器学习算法。由于错误模型，拼写检查器可以计算p(w|c)，即用户在键入w时意思是键入某个英语单词c的概率。
将所有这些内容结合起来，拼写检查器将能够为用户在出错时意图输入的内容生成几个可能的建议。这些建议将再次受到某个模糊函数的限制，该函数指定哪些建议应被视为“可能”，哪些不应被视为。如果算法是好的，建议将是准确的。
其他模糊匹配算法旨在以与levenshtein距离函数相同的最终效果，但以不同方式使用模糊概念。例如，soundex和metaphone算法在读出时寻找听起来像其他字符串的字符串，但其拼写不同。为此，这些算法需要大量的听觉数据，可以将其缩小到频率。然后，它们通过近似匹配比较这些频率，这可能非常类似于levenshtein距离函数。从这些数据中，它们对哪些字符串听起来像哪些其他字符串做出判断。
原则上，这概述了所有模糊匹配的基本原理。应用范围可能从拼写检查到合并具有相似字符串的数据库，再到根据您通过手机麦克风哼唱的歌曲的名字。在所有情况下，模糊匹配是基本原理。
如何创建模糊匹配程序？
模糊匹配的程序通常使用java和python等编程语言编写。如果您想知道如何编写这样的程序，可以在整个互联网上找到教程。这个特定的视频教程介绍了字符串相似性算法的结构以及它们在java中的实现方式。那里考虑的特定算法被称为余弦相似度算法。该算法依赖于任何两个非零向量之间的差异可以表示为它们之间夹角的余弦。因此，如果两个向量v和w平行于彼此-即它们之间的角度为0-则它们被认为是相等的，如果它们是彼此正交的-即它们之间的角度为90度-则它们被认为是最不相似的。这是因为cos(0)=1，cos(90)=0。因此，cos(θ)的值对应于任何与它们之间形成角度θ的两个向量之间的相似程度。
这个java算法的工作原理是将两个字符串分割成n-gram表示，将每个字符串的每个n-gram编码成向量，然后通过计算它们关联向量的点积来比较每个字符串的对应n-gram。这个方法的原理是因为两个向量v和w的点积等于它们之间夹角的余弦。
这个其他的教程介绍了一个特殊的python库，称为fuzz，您可以安装和使用它来帮助您在python中进行模糊匹配。这个库使用的特定算法依赖于上面描述的levenshtein距离函数。
模糊匹配的起源和发现
对于涉及模糊匹配出现的历史事实的任何讨论都会涉及到模糊逻辑本身的一般历史，所以我们只是涉及到了大致的情况。如果您对模糊逻辑的历史和发展更深入的讨论感兴趣，请阅读radim belohlavek、joseph w. dauben和george j. klir合著的书籍模糊逻辑与数学：历史的视角。这本书不仅提供了丰富有趣的历史细节，还对这个主题本身进行了优秀而严谨的讨论。
模糊逻辑与数学：历史的视角
$156.75
- 由radim belohlávek、joseph w. dauben和george j. klir教授撰写
- 由牛津大学出版社出版
- kindle版
- 研究模糊逻辑的起源和发展
在amazon购买
如果您购买，我们将获得佣金，您不需要额外付费。
最早记录下来的激发模糊逻辑的想法是由被广泛认为是古典逻辑之父的亚里士多德提出的。在他的逻辑论著中的一篇文章中，亚里士多德认识到未来的可能性——也就是形如“如果我下个月去巴黎度假，我会在那里遇到未来的妻子”这样的陈述——对于只处理“真”和“假”这两种具体真值的逻辑来说，是一个棘手的问题。虽然将这些陈述看作具有真值是合理的，但这些陈述涉及尚未发生的事件，其真值并不清楚——甚至可能永远不会发生。如果说这样的陈述在现在既不能说是真的也不能说是假的，那它们有其他的真值吗？
在其他的文章中，亚里士多德还认识到模糊性、边界情况和其他问题可能会使标准古典逻辑变得复杂。然而，他选择将这些问题搁置一边，继续发展古典逻辑。
后来，在14世纪，神学家、哲学家和逻辑学家威廉·奥卡姆在他的《论预定论、上帝的先知和未来的可能性》一书中，通过复杂的论证表明亚里士多德关于未来可能性的陈述意味着存在着既非真也非假但具有第三种真值的陈述。然而，与亚里士多德一样，奥卡姆选择不再深入探讨这种思维方式。
尽管偶尔对古典逻辑的局限性有所觉察，逻辑在许多世纪里以标准的方式发展，基本上保持了乔治·布尔的理论直到几十年前。
1965年，阿塞拜疆和苏联数学家洛特菲·扎德发表了一篇开创性论文，首次阐述了我们所讨论的模糊逻辑和数学的所有基本概念，以及其他一些概念。扎德在1940年代和1950年代从事系统理论、控制理论、信息理论、电路分析和电气工程的研究，最终质疑了标准数学在复杂系统中的适用性。受生物学家、一般系统理论创始人路德维希·冯·贝塔兰菲的工作启发，扎德试图设计一种能够描述不易精确度量的事物的数学系统。尽管他的观点最初遭到抵制，但现在已被广泛接受。
与扎德在模糊逻辑和集合论上发表论文的同一年，俄罗斯-苏联数学家和科学家弗拉基米尔·列文斯坦在信息理论和纠错码领域进行自己的研究时，提出了“列文斯坦距离”的概念和计算函数。
将这些思想结合起来导致了模糊匹配的诞生。
模糊匹配的应用
我们已经讨论了一些模糊匹配的应用，这里简要概述一下，并添加了一些其他应用。模糊匹配用于：
- 拼写检查软件
- 搜索引擎（为拼写错误的搜索查询提供最佳结果）
- 关系数据库管理（用于合并客户记录，检查重复记录等）
- 家谱搜索
- 像shazam这样的歌曲识别应用
shazam是一款使用模糊匹配来“听取”正在播放的音乐并显示特定歌曲的标题和艺术家的应用。
©allmy/shutterstock.com
现实世界中的模糊匹配
以下是与模糊匹配相关的抽象概念如何影响现实世界的一些解释。
在一个相当著名且爆炸性的案例中，美国联邦航空管理局（faa）使用模糊字符串匹配算法检测到了一起大规模的欺诈案件。faa研究了一个包含40,000名生活在加利福尼亚北部的飞行员姓名的大型数据库，并将这些姓名与正在领取社会保障残疾金的人员名单中的姓名进行比对。由于在残疾状态下驾驶飞机或欺诈领取残疾金都是违法行为，因此在两个数据库中都找到姓名的40名飞行员由此被逮捕，其中14名飞行员的执照被吊销。如果没有模糊匹配，这起欺诈案件很可能不会被发现。
模糊匹配在基因组测序中也非常有帮助。如果研究人员需要确定特定基因组序列属于哪个群组，他们可以在序列上启动模糊匹配算法，找到最近的其他序列或一组序列，然后根据结果对未知序列所属的生物种类进行有根据的猜测。
希望通过合并不同的客户数据库来为重复或常规客户创建单一客户视图（svc）的企业可以借助模糊匹配来实现。这样一来，他们可以更高效地为常客提供服务，并对其可能想要的其他产品提供更有效的建议。
