README

这实现了德国哈索普拉特纳研究所、波茨坦和柏林洪堡大学计算机科学系Dandy Fenz、Dustin Lange、Astrid Rheinländer、Felix Naumann和Ulf Leser在2012年研究论文《在非常大的字符串集中进行高效的相似性搜索》中提出的算法。

该算法允许在保持索引大小小的同时，有效地搜索包含错误（Levenshtein距离）的大量数据集。 在此处下载论文并阅读所有细节。

安装

使用Composer

composer require toflar/state-set-index

用法

namespace App;

use Toflar\StateSetIndex\Alphabet\Utf8Alphabet;
use Toflar\StateSetIndex\DataStore\InMemoryDataStore;
use Toflar\StateSetIndex\StateSet\InMemoryStateSet;
use Toflar\StateSetIndex\StateSetIndex;

$stateSetIndex = new StateSetIndex(
    new Config(6, 4),
    new Utf8Alphabet(),
    new InMemoryStateSet(),
    new InMemoryDataStore()
);

$stateSetIndex->index(['Mueller', 'Müller', 'Muentner', 'Muster', 'Mustermann']);
$stateSetIndex->find('Mustre', 2); // Will return ['Muster'];

配置

您可以使用Config对象配置最大索引长度和最大字母表大小。请阅读论文了解它们的详细作用。没有推荐的尺寸，因为它在很大程度上取决于您想要索引和/或搜索的内容。

定制

此库附带已为您准备好的算法，供您使用。主要的定制区域将是字母表（它将字符映射到标签的方式）和状态集存储，如果您想使索引持久化。因此，有两个接口允许您实现自己的逻辑。

• AlphabetInterface非常简单直接。它只包含一个map(string $char, int $alphabetSize)方法，该库需要将字符映射到内部标签。是否在数据库中加载/存储字母表取决于您。库附带一个InMemoryAlphabet供参考和简单用例。您甚至不需要存储字母表，因为我们已经有一个带有UTF-8代码点的字母表，这就是Utf8Alphabet的作用。如果您不想定制标签，请使用Utf8Alphabet。
• StateSetInterface负责加载和存储有关索引状态集的信息。同样，您如何在数据库中加载/存储状态集取决于您。库附带一个InMemoryStateSet供参考和简单用例以及测试。
• DataStoreInterface负责存储您索引的字符串及其分配的状态。有时您想完全自定义存储，在这种情况下，您可以使用NullDataStore并仅使用从调用$stateSetIndex->index()获得的分配作为返回值。

您不仅可以使用$stateSetIndex->findMatchingStates('Mustre', 2)请求最终匹配结果，该结果已经使用多字节Levenshtein算法进行过滤，还可以访问中间结果，您可以使用这些结果来例如搜索自己的数据库中的状态等。

• $stateSetIndex->findMatchingStates('Mustre', 2)仅返回匹配的状态。
• $stateSetIndex->findAcceptedStrings('Mustre', 2)返回匹配的状态以及相应的接受字符串（未过滤以避免错误阳性！）。
• $stateSetIndex->find('Mustre', 2)返回真正的匹配项，并过滤掉错误阳性。