我们都会犯错误：在这种情况下，我们正在谈论搜索查询。 随用户需求的增长，用于销售商品和服务的站点的数量在增加，但是他们并不总是能找到他们想要的东西-仅仅是因为他们错误地输入了必要产品的名称。 通过实施模糊搜索，即考虑到用户可能的错误或错字，使用查找最接近值的算法来实现此问题的解决方案。 这样的搜索范围足够广泛-我们设法在食品零售领域搜索大型在线商店。
初始搜索状态
在线商店是在1C-Bitrix：站点管理平台上开发的。 为了实现搜索，我们使用了标准的bitrix搜索模块和sphinxsearch全文引擎。 在sphinxsearch中，使用了实时（RT）索引类型，该类型不需要静态数据源，但可以随时实时填充。 这使您可以灵活地更新搜索索引，而无需完全重新索引它。 由于RT索引仅使用SphinxQL作为查询协议，因此通过它进行了集成。 SphinxQL是一种类似于mysql的查询协议，该协议实现了通过标准mysql客户端进行连接的能力，同时为sql语法提供了一些限制和自身的特点。 搜索模块使用选择/插入/替换/删除查询。
在bitrix系统中，执行了对商品，类别和品牌数据进行索引的过程。 这些实体的信息已传输到狮身人面像，狮身人面像又更新了RT索引。 在在线商店中更新数据时，将触发一个事件，该事件将更新Sphinx中的数据。 数据的一致性是通过在线商店中的实体标识符来实现的。
当用户在在线商店中搜索时，系统会在Sphinx中使用搜索短语发出请求，并获取实体的标识符，还从数据库中选择关于实体的信息，并形成包含搜索结果结果的页面。
在开始解决模糊搜索问题时，该项目上搜索体系结构的一般方案如下：
技术选择
我们的任务是猜测用户的请求，其中可能包含错别字。 为此，我们需要分析请求中的每个单词并确定用户是否正确编写了单词。 发生错误时，应选择最合适的选项。 没有单词和我们想用来猜测它们的语言的单词形式的数据库，就不可能确定单词的正确拼写。 简单地说，这样的数据库可以称为字典-我们需要的就是他。
为了为输入错误的单词选择替换选项，选择了流行的Damerau – Levenshtein距离计算公式。 该公式是用于比较两个单词的算法。 比较的结果是将一个单词转换为另一个单词的操作次数。 最初，Levenshtein距离涉及使用3个操作：
Damerau-Levenshtein距离是Levenshtein距离的扩展版本，并增加了另一个操作：换位，即两个相邻字符的置换。
因此，接收到的操作数变成了用户在写单词时所犯的错误数。 我们选择了两个错误的限制，因为更大的错误数目是没有意义的：在这种情况下，我们有太多的替换选项，这增加了遗漏的可能性。
为了更相关地搜索声音相似的单词的变体，使用了变音位功能-该功能将单词转换为语音形式。 不幸的是，metaphone仅适用于英文字母，因此在计算语音形式之前，我们先对单词进行音译。 语音形式的值存储在字典中，也可以根据用户的请求进行计算。 将结果值与Damerau-Levenshtein距离函数进行比较。
字典存储在MySQL数据库中。 为了不将字典加载到应用程序内存中，决定计算基准侧的Damerau-Levenshtein距离。
在 Linus Torvalds编写的C函数的基础上编写的
用于计算Damerau-Levenshtein距离的用户定义函数完全满足了我们的要求。 由迭戈·托雷斯（Diego Torres）创建。
在计算了Damerau-Levenshtein距离之后，有必要根据相似度对结果进行排序以选择最合适的结果。 为此，我们使用了Oliver算法：计算两条线的相似度。 在php中，此算法由相似文本函数表示。 函数的前两个参数接受需要比较的输入行，字符串比较的顺序很重要，因为函数根据将行传递给函数的顺序给出不同的值。 第三个参数应传递比较结果所在的变量。 这是一个从0到100的数字，表示两行之间的相似性百分比。 计算后，结果按照相似度从高到低的顺序排序，然后选择具有最佳值的选项。
由于根据单词的转录进行了Damerau-Levenshtein距离的计算，因此含义不完全相关的单词成为结果。 在这方面，我们限制了匹配百分比超过70％的选项的选择。
在开发过程中，我们注意到我们的算法可以猜测不同布局中的单词。 因此，我们需要通过在反向布局上添加单词的含义来扩展字典。 搜索要求仅具有两种布局：俄语和英语。 我们在反向布局上重复了用户搜索查询的每个单词，并添加了用于计算Damerau-Levenshtein距离的处理。 正向和反向布局的选项彼此独立处理，选择相似度最高的选项。 仅对于反向布局选项，直接布局中的值才是更正后的搜索查询的值。
模糊搜索算法
因此，形成了六个主要步骤的动作算法。 在测试过程中，我们发现并非用户请求中的所有单词都需要以其原始形式或一般方式进行处理。 为了解决这种情况，我们引入了另一个步骤，我们将其称为转换器或滤波器。 结果，最终算法包括7个步骤：
- 将查询分为几个单词；
- 将每个单词传递给转换器（进一步了解）；
- 对于每个单词，将其形式设置为不同的布局；
- 撰写转录；
- 在字典表中进行搜索查询，比较通过Damerau-Levenshtein距离的每个条目；
- 仅保留距离小于或等于2的记录；
- 通过Oliver算法，仅保留相似度超过70％的单词
示意地，该算法如下：
文字转换和过滤功能
当我们开始测试没有转换器的第一个原型时，很明显，无需尝试猜测用户请求中的所有单词。 已针对这些限制创建了转换器。 它使您可以将单词转换为我们需要的形式，并过滤掉我们认为不需要猜测的单词。
最初，决定应通过算法的最小字长至少应为两个字符。 毕竟，如果用户输入一个借口或一个字符的并集，则猜测的可能性实际上很小。 第二步是将查询分为单词。 首先，我们选择了一组可以包含单词的字符：字母，数字，句点和连字符（破折号）。 空格和其他字符是单词定界符。
用户经常输入数字来指示数量或数量。 在这种情况下，更正这种请求将是不正确的。 例如，用户输入查询“ 1.1升水”。 如果我们以1.5或1.0纠正他的要求，那将是错误的。 在这种情况下，我们决定跳过带数字的单词。 它们绕过我们的算法，被转移到全文Sphinx搜索中。
另一种转换与品牌名称中的点相关联-例如：Pepper博士或Mr.Proper。 如果单词中间有一个点号，则我们将其分成两个，并添加一个空格。 第二种情况是在单词中间加一个点-在这里我们想起缩写品牌。 例如，ROCS品牌-在这种情况下，我们切掉了圆点并得到了一个单词。 如果点之间只有一个字母，则此转换有效。
如果单词中出现连字符（破折号），则应将单词分成几个单词，并尝试分别猜测它们，然后将最佳选择粘合在一起。
结果，开发了一个转换器来最准确地识别请求-设置所有功能的大部分工作都由此特定开发完成。 非常感谢他，可以执行整个模糊搜索的调整和调整。 简要重复执行筛选和单词转换的规则：
- 单词必须超过2个字符
- 该单词应仅包含字母，句点字符和连字符（破折号）
- 如果点在单词的中间，则在其后添加一个空格
- 如果是缩写，则切去点，然后将字母粘在一起
- 如果单词中有数字，请勿尝试猜测
- 如果单词包含连字符（破折号），则将其分成几个，分别搜索并在末尾粘贴
字典编译
如前所述，为了更正用户的请求，有必要确定哪些单词拼写错误而哪些单词拼写错误。 为此，在系统中创建了一个字典，其中应包含具有正确拼写的单词。
在第一阶段，出现了填写字典的问题-结果，我们决定使用目录内容来对其进行编译。 由于不时从外部系统导入商品信息并为Sphinx全文搜索系统建立索引，因此决定在此阶段添加词典编辑功能。 我们遵循以下逻辑：如果单词不在商品的内容中，那么为什么要猜测呢？
产品信息被组合成一个普通文本，并通过转换器进行处理。 转换器的操作模式稍作修改：通过连字符（破折号）打断单词时，每个部分分别保存在词典中，替换词典中的点时，将添加原始数据和更改的数据。 而且，由于在比较单词以计算Damerau-Levenshtein距离时，除了字典外，还使用了单词的转录，因此添加了转录。
产品内容中有很多错别字，为此，在字典中放置了一个标志，安装后，该词不再在搜索中使用。 来自35,000种产品的内容允许创建包含10万个唯一单词的字典，最后对于某些用户查询而言还不够。 在这方面，有必要提供加载功能以使其富集。 创建了一个控制台命令来加载字典。 带有字典数据的文件格式应对应于csv。 每个条目仅包含一个字段，而字典字段本身。 为了将下载的数据与基于商品内容生成的数据区分开，添加了一个特殊标志。
结果，字典表具有以下方案：
| 栏位名称 | 栏位类型 |
|---|
| 这个词 | 弦 |
| 转录 | 弦 |
| 手动添加 | 布尔 |
| 不要使用 | 布尔 |
在开发模糊搜索功能之前，产品中的某些字段包含一组带有错字的单词。 在字典生成的第一轮中，他们进入了字典的内容。 结果，获得了带有错别字的字典，其内容不适合该功能正常工作。 因此，添加了另一个具有反向字典生成功能的控制台命令。 利用给定商品领域的内容，团队在词典中搜索单词并将其从词典中清除。 清洗后，将这些字段排除在索引之外。
Bitrix整合
为了实现所需的最低功能，创建了三个类：
- DictionaryTable-使用字典的Bitrix ORM系统
- 字典-字典生成类
- 搜索-搜索实现类
为了集成到Bitrix，需要对2个组件进行更改：
- bitrix：search.page
- bitrix.search.title
在执行请求之前，将调用处理方法以检测错误并选择适当的选项：
为了编译字典，记录了一个事件，以供搜索模块将带有商品的信息块的元素建立索引（搜索：BeforeIndex）。
未来计划
就性能而言，此方法并不理想。 随着字典大小增加到1M +单词，数据库的响应时间会大大增加。 虽然字典很小，但性能适合我们。 将来可能需要通过Levenshtein自动机或前缀树来实现该算法。
结论
因此，任何搜索引擎都不会幸免出现违反普遍接受的拼写规则的查询-无论是随机的拼写错误还是真正缺乏单词拼写知识。 因此，您甚至无需借助经典的模糊搜索选项Google或Yandex，就可以创建自己的模糊搜索选项，这使得用户和网站所有者都能够获得所需的结果。
我们的实现代码可以在存储库中查看：
github.com/qsoft-dev/damlev-bitrix