神秘对手：模糊借用

非法借贷是一种多头的蛇蝎，是不断改变面容的敌人。 我们最好的私家侦探随时准备抓住这个敌人所犯的任何罪行。 但是，敌人没有睡觉，他狡猾而狡猾：很明显，他用一件事代替了他，巧妙地将痕迹扫了进去。 有时，在我们最灵活的员工Suffix Massiv的帮助下，他设法捉住了手。 有时敌人会犹豫，而细致却悠闲的Search for Paraphrase设法计算出其位置。 但是邪恶是阴险的，我们不断需要新的力量来对抗它 。

今天，我们将谈论我们的新特警“ 模糊搜索” ，以及他第一次接触模糊借贷。

与您的侦探社Anti窃 ，为神秘对手案做好准备

场景

在检查区域（文档）时， 反P窃行为会检查该区域是否有任何关于可能的犯罪的电话。 能带给我们有关犯罪信号的目击者是带状疱疹指数 。

“带状疱疹是一段文本，只有几个单词的大小。” 每个这样的片段都经过散列处理，并在索引中搜索具有带有与正在检查的文档中相同的哈希的带状疱疹的文档。

目击者看到两个带状疱疹的巧合，给我们打了个关于犯罪的信息。 不幸的是，带状疱疹指数不能因错误的举报而受到惩罚，它不受制裁的制裁，这就是为什么有很多举报的原因。 该机构确定此类电话中堆积最多的文件-潜在犯罪现场。

第一条线索

现在你是个侦探，儿子。
从现在开始，您被禁止相信巧合。

侦探模糊搜索到达犯罪现场。 足够大的犯罪分子不会被忽视，因为犯罪规模越大，就越有可能留下线索。 对于模糊搜索，此类潜在客户是固定长度的短匹配项。 似乎我们的侦探缺少大量熟练地扫除犯罪分子的痕迹，但只有5％的攻击者没有留下这样的线索。 重要的是不要丢下罪犯，因此侦探使用一种特殊的检测火柴的技术快速扫描了该区域。

侦探关于工作方法的日记。 第一阶段

我们将使用任务的两个功能：

1. 我们对固定长度的清晰重复感兴趣。
2. 在一个好的文档中，同一个木瓦不会重复太多。

第二个条件对于限制找到的清晰重复项的数量是必要的。 实际上，在文档中和源中出现1000次的单个匹配项将提供1,000,000对匹配项。 仅在尝试爬网的未清理文档中才能看到这种频繁重复的带状疱疹。

清除爬网的文档以单词顺序显示。 我们将单词带入正常的单词形式，然后对其进行哈希处理。 我们得到一个整数序列（在gif上-一个字母序列）。 对该序列的所有带状对象进行哈希处理，并将其与子字符串开头位置的值一起输入到哈希表中。 然后，对于候选文档中的每个瓦片，在哈希表中找到匹配项。 这将创建固定长度的清晰重复项。 与后缀数组相比，使用新方法进行的测试显示出三倍的加速度。

我们计算罪犯

-您还建议我注意其他几点吗？
“狗在犯罪当晚的奇怪行为。”
-狗？ 但是她没有任何表现！
“那很奇怪，”福尔摩斯说。

_{©Arthur Conan-Doyle，“银”（摘自“福尔摩斯笔记”系列）}

因此，模糊搜索找到了一些识别罪犯的线索。 我们的英雄会充分利用其演绎能力，以便根据发现的线索一点一点地逐渐恢复罪犯的形象。 侦探正在逐步扩展正在发生的事情的图像，用新的细节对其进行补充，发现越来越多的证据，直到该图像最终完成。 我们的侦探有时会被带进来，他必须从天上降下来，并确信我们需要罪犯的身份，而不是他堂兄的传记。 模糊搜索会发出抱怨，但会谦虚地将图片缩小到所需的比例。

侦探关于工作方法的日记。 第二阶段

_{图像来源： Foto.com}

第二阶段在文档中左右分配重复项。 分布来自“中心”-找到明确的重复项。 为了比较后缀，我们使用Levenshtein距离 -将一行带到另一行所需的单词删除/替换/插入的最小数量。 基于Levenshtein距离的递归确定，可以使用Wagner-Fisher算法动态计算重复后缀的距离。 但是，该算法的复杂度是二次的，并且不允许控制错误的比例。 另一个问题是重复项边界的确切定义。 为了解决这些问题，我们使用了一些简单但有效的程序。

在此步骤中，建议首先为模糊重复后缀（然后，类似地，对于前缀）依次填充Levenshtein距离矩阵。 因为我们检查后缀的“相似性”，所以我们只对矩阵对角线附近的值感兴趣（Levenshtein距离大于或等于线长的差）。 这允许线性复杂度。 设置最大允许Levenshtein距离后，我们将填写表格，直到遇到列中的值大于允许值的列为止。 这样的一列表明我们的模糊重复项最近结束了，并且单词几乎完全重合。 在为每个填充的单元格保存了先前的最优值之后，我们从临界列中具有最小惩罚的单元格开始下降，直到找到多个匹配项，此后误差开始急剧增加。 这些将是找到的模糊重复项的边界。

另外，为了避免错误累积，引入了一种程序来重置错误数量，如果我们从连续的巧合中偶然发现“孤岛”，则会再次开始传播。

犯罪团伙

-明天我们计划与同学聚会！
-在一个大同学里？
-什么？

_©Bashorg

模糊搜索仍然是一项简单的任务：将在同一地点被抓的犯罪分子联合起来，为无辜嫌疑人辩护，并将结果汇​​总在一起。

_{图像来源： Foto.com}

粘贴重复项可以立即解决3个问题。 首先，“复制品分发”的第二阶段吸收了单词和短语的修饰，而不是整个句子的修饰。 如果您增加算法的“扩展能力”，则它将开始在相距太远的巧合上扩展，并且重复项的边界将被确定为更差。 因此，我们失去了对我们如此重要的精确度，而这正是我们明确寻找的目标。

其次，第二阶段无法识别两个重复项的排列。 我希望在某些地方对这两个句子进行排列以形成接近原始句子的短语，但是对于一行唯一字符而言，在某些地方对前缀和后缀进行排列会导致该行尽可能远离原始行（以Levenshtein度量标准）。 事实证明，第二阶段在重新排列句子时会找到两个彼此相邻的重复项，您希望将它们合并为一个。

第三个原因是粒度或粒度。 粒度是一种度量，它确定在我们发现的真实贷款中发现的重复项的平均数量。 换句话说，粒度表明我们找到整个借贷而不是覆盖其中的几个部分的情况。 粒度的正式定义以及微观平均准确性和完整性的定义可以在文章“窃检测的评估框架”中找到 。

Gifka显示，有时只有在其中一个粘贴到第三个副本之后才能粘贴两个副本。 因此，在文档上从左到右仅进行一次遍历就无法完成粘合。

初学者训练

侦探需要适应我们城镇的特征，适应地形，沿着不起眼的街道散步并更好地了解其居民。 为此，初学者参加了特殊的培训课程，他在训练场上研究了类似的情况。 侦探在实践中研究线索，演绎和建立社会纽带，以最有效地抓捕罪犯。

参数模型需要优化。 为了确定最佳模型参数，使用了PlagEvalRus样本 。

该样本分为4个集合：

• Generated_Copypast（4250对）-逐字生成借入
• Generated_Paraphrased（4250对）-机器使用原始段落的噪声（任意替换/删除/插入）生成的弱和中度修改借入
• Manually_Paraphrased（713对）带有各种借用类型的手写文本，主要是弱而中等修改的借用内容（替换为不超过重复单词的30％）
• Manually_Paraphrased 2（198对）带有中等和高度修改（超过30％单词）借阅的手写文本

使用多起点下降法进行最佳模型参数的搜索。 最大化 $$$F_ \ beta$用...测量 $$$\ beta ^ 2 = \ frac {1} {4}$（强调准确性）。 这是最重要的最佳参数。

病历

模糊搜索的试用期已经结束。 让我们将它的生产率与另一个侦探Suffix Array的生产率进行比较。 培训课程模糊搜索在Manually_Paraphrased程序上进行。

在现场，新来者在解决案件的比例上显示出明显的优势。 他的工作速度也不能不令人高兴。 我们的代理机构缺乏如此宝贵的员工。

将模型的质量与后缀数组进行比较，我们发现粒度有了显着改善，并且更好地检测了中度和高度修改的借入。

在不超过10 ^7个字的文档上进行测试，我们验证了这两种算法的线性。 在i5-4460处理器上，该程序在不到一秒钟的时间内处理了一对百万字的“文档源”。

生成带有大量借用的文本后，我们确信模糊搜索（蓝线）并不比后缀数组（红线）慢。 相反，在大型文档中，后缀数组的重复项过多。 我们比较了最少5个字的重复长度的效果。 但是，为了获得足够的借阅范围，我们使用清晰的搜索词，且重复词的最小长度为3个字，这在庞大的文档上会导致生产率显着下降（橙色线）。 值得注意的是，普通文件包含的借用较少，并且在实践中这种影响不那么明显。 但是这样的实验使我们能够通过新的模糊搜索来理解模型的适用性扩展。

范例：

可以看出，尽管计算复杂度很小，该算法仍能处理替换/删除/插入的检测，第三步使您可以检测句子及其组成部分的排列变化。

结语

Fuzzy Search与我们的其他工具一起工作在一个团队中：快速搜索候选文档，提取文档格式，大规模捕获旁路尝试。 此命令使您可以快速发现潜在的抄袭。 模糊搜索已扎根在这个团队中，其定性搜索功能比后缀数组更具有定性，而且更重要的是，它的执行速度更快。 我们的机构将更好地应对其任务，不道德的作者在使用非原创文字时会遇到新的问题 。

用自己的思想创造！