0

我正在寻找一种算法和存储模式来对大于内存的字典进行字符串匹配。

受https://swtch.com/~rsc/regexp/regexp4.html启发，我最初的尝试是存储字典中每个单词的三元组，例如在索引时将单词拆分为apple、$ap、app和。所有这些三元组都与它们来自的单词相关联。pplplele$

然后我查询时间，我对必须匹配的输入字符串做同样的事情。我在数据库中查找每个三元组，并将候选词存储在与其中匹配三元组数量相关的映射中。然后，我继续计算每个候选人之间的 levenshtein 距离并应用以下公式：

score(query, candidate) = common_trigram_number(query, candidate) - abs(levenshtein(query, candidate))

这种方法有两个问题，首先候选选择太宽泛。其次，levenshtein 距离太慢而无法计算。

修复第一个，可能会使第二个无法优化。

我想到了另一种方法，在索引时，我将存储单词（可能与频率相关），而不是存储三元组。在查询时，我可以query使用 levenshtein 和频率查找字符串的连续前缀和分数。

特别是，我不是在寻找一种算法，它可以为我提供距离为 1、2 等的字符串......我只想从字典中获得一个或多或少相关单词的分页列表。实际选择由用户进行。

此外，它必须可以用有序的键值存储来表示它，如rocksdb 或wiredtiger。

4

1 回答 1

0

simhash 捕获（小）字符串之间的相似性。但它并没有真正解决在大于 RAM 的数据集中查询最相似字符串的问题。我认为，原始论文建议对一些排列进行索引，它需要大量内存并且没有利用 OKVS 的有序特性。

我想我找到了一个允许在哈希前缀内捕获相似性的哈希：

In [1]: import fuzz                                                                                      

In [2]: hello = fuzz.bbkh("hello")                                                                       

In [3]: helo = fuzz.bbkh("helo")                                                                         

In [4]: hellooo = fuzz.bbkh("hellooo")                                                                   

In [5]: salut = fuzz.bbkh("salut")                                                                       

In [6]: len(fuzz.lcp(hello.hex(), helo.hex())) # Longest Common Prefix                                                      
Out[6]: 213

In [7]: len(fuzz.lcp(hello.hex(), hellooo.hex()))                                                        
Out[7]: 12

In [8]: len(fuzz.lcp(hello.hex(), salut.hex()))                                                          
Out[8]: 0

在对 wikidata 标签进行小规模测试后，它似乎给出了很好的结果：

$ time python fuzz.py query 10 france
* most similar according to bbk fuzzbuzz
** france    0
** farrance      -2
** freande   -2
** defrance      -2

real    0m0.054s

$ time python fuzz.py query 10 frnace
* most similar according to bbk fuzzbuzz
** farnace   -1
** france    -2
** fernacre      -2

real    0m0.060s

$ time python fuzz.py query 10 beglium
* most similar according to bbk fuzzbuzz
** belgium   -2

real    0m0.047s


$ time python fuzz.py query 10 belgium
* most similar according to bbk fuzzbuzz
** belgium   0
** ajbelgium     -2

real    0m0.059s

$ time python fuzz.py query 10 begium
* most similar according to bbk fuzzbuzz
** belgium   -1
** beijum    -2

real    0m0.047s

这是一个实现：

HASH_SIZE = 2**10
BBKH_LENGTH = int(HASH_SIZE * 2 / 8)

chars = ascii_lowercase + "$"
ONE_HOT_ENCODER = sorted([''.join(x) for x in product(chars, chars)])


def ngram(string, n):
    return [string[i:i+n] for i in range(len(string)-n+1)]


def integer2booleans(integer):
    return [x == '1' for x in bin(integer)[2:].zfill(HASH_SIZE)]


def chunks(l, n):
    """Yield successive n-sized chunks from l."""
    for i in range(0, len(l), n):
        yield l[i:i + n]


def merkletree(booleans):
    assert len(booleans) == HASH_SIZE
    length = (2 * len(booleans) - 1)
    out = [False] * length
    index = length - 1
    booleans = list(reversed(booleans))
    while len(booleans) > 1:
        for boolean in booleans:
            out[index] = boolean
            index -= 1
        new = []
        for (right, left) in chunks(booleans, 2):
            value = right or left
            new.append(value)
        booleans = new
    return out


def bbkh(string):
    integer = 0
    string = "$" + string + "$"
    for gram in ngram(string, 2):
        hotbit = ONE_HOT_ENCODER.index(gram)
        hotinteger = 1 << hotbit
        integer = integer | hotinteger
    booleans = integer2booleans(integer)
    tree = merkletree(booleans)
    fuzz = ''.join('1' if x else '0' for x in tree)
    buzz = int(fuzz, 2)
    hash = buzz.to_bytes(BBKH_LENGTH, 'big')
    return hash


def lcp(a, b):
    """Longest Common Prefix between a and b"""
    out = []
    for x, y in zip(a, b):
        if x == y:
            out.append(x)
        else:
            break
    return ''.join(out)

评估：使用维基百科常见的拼写错误单词，大约有 8k 个单词。考虑前 10 个最接近的词，每个查询大约需要 20 毫秒，成功率达到 77%。考虑到前 100 名，每个查询花费的时间不到 200 毫秒，成功率为 94%。大多数错误来自连接词（例如“abouta”而不是“about a”）或用破折号分隔的词。

在https://github.com/amirouche/fuzzbuzz/blob/master/typofix.py查看代码

注意：计算 simhash 而不是输入字符串，仅适用于一袋引理或词干，实际上它会找到类似的文档。

于 2019-11-10T18:48:07.597 回答