2

我想使用 Python 中的文本数据集在 Levenshtein 距离上执行最近邻搜索。搜索可以是近似的，应该使用核心 Python 库来实现，并且查询应该是接近恒定时间的操作。下面，我列出了一些我考虑过的实现以及它们的缺陷。

天真的蛮力方法

一个天真的蛮力解决方案涉及计算查询和数据集中所有文本之间的成对 Levenshtein 距离：

$ pip install numpy python-Levenshtein
$ python
>>> import Levenshtein
>>> import numpy as np
>>>
>>> texts = ["Some string", "Some other string", "Yet another string"]
>>> query = "Smeo srting"
>>> knn = 2
>>>
>>> distances = [Levenshtein.distance(query, text) for text in texts]
>>> for idx in np.argsort(distances)[:knn]:
...     print(f'{texts[idx]}, {distances[idx]}')
...
Some string, 4
Some other string, 8

然而，幼稚的方法相当缓慢。对于最大文本长度为 N 的 M 个文本，搜索查询的 K 个最近邻是 O(M * N^2) 操作。为 M 个文本中的每一个找到 K 个最近的邻居是一个 O(M^2 * N^2) 操作。

指标索引

我考虑的一种解决方案是指标索引。度量索引为度量空间中的 K-最近邻搜索提供了比初始速度更好的速度。被索引的单位不必是向量，只需配上距离函数，形成度量空间即可。配备 Levenshtein 距离的字符串形成一个度量空间。

度量学习的一个很好的特性是它在核心 Python 库中实现，例如在sklearn.neighbors.BallTree. 使用球树，搜索 a 的 K 个最近邻居变成了 O(log M * N^2) 操作。为 M 个文本中的每一个找到 K 个最近的邻居是一个 O(M log M * N^2) 操作。

sklearn 实现的一个缺点是它需要输入浮点向量。因此，似乎需要从字符串到浮点向量并返回的映射方案。该解决方案可以表示多达 2^53 个字符串的数据集，这似乎足够了：

$ pip install sklearn python-Levenshtein
$ python
>>> from typing import Optional
>>> import Levenshtein
>>> import numpy as np
>>> from sklearn.neighbors import BallTree, DistanceMetric
>>> 
>>> texts = ["Some string", "Some other string", "Yet another string"]
>>> query = "Smeo srting"
>>> knn = 2
>>> 
>>> def text_to_vector(text: str, idx: Optional[int] = None) -> np.ndarray:
...     if idx is None:
...         idx = len(texts)
...         texts.append(text)
...     return np.array([idx], dtype=np.float64)
... 
>>> def vector_to_text(idx: np.ndarray) -> str:
...     return texts[int(idx[0])]
... 
>>> def levdist(x: np.ndarray, y: np.ndarray) -> int:
...     x, y = map(vector_to_text, (x, y))
...     return Levenshtein.distance(x, y)
... 
>>> X = [text_to_vector(text, idx) for idx, text in enumerate(texts)]
>>> x = [text_to_vector(query)]
>>> 
>>> tree = BallTree(X, metric=DistanceMetric.get_metric('pyfunc', func=levdist))
>>> (dists,), (idxs,) = tree.query(x, k=knn)
>>> for dist, idx in zip(dists, idxs):
...    print(f'{texts[idx]}, {int(dist)}')
... 
Some string, 4
Some other string, 8

但是，速度似乎仍然是一个主要缺点。我会很感激指向在接近 O(M * N^2) 时间的 Levenshtein 距离或度量空间上提供近似 K-最近邻搜索的库的指针。

4

0 回答 0