Ghi*_*ADJ 18 python distance match n-gram
我正在寻找一个库或使用现有库的方法(difflib,fuzzywuzzy,python-levenshtein)中查找的字符串(的最接近的匹配query)文本(corpus)
我开发了一个基于的方法difflib,我将其corpus分成大小n(长度query)的ngrams .
import difflib
from nltk.util import ngrams
def get_best_match(query, corpus):
ngs = ngrams( list(corpus), len(query) )
ngrams_text = [''.join(x) for x in ngs]
return difflib.get_close_matches(query, ngrams_text, n=1, cutoff=0)
当查询和匹配字符串之间的差异只是字符替换时,它可以按我的意愿工作.
query = "ipsum dolor"
corpus = "lorem 1psum d0l0r sit amet"
match = get_best_match(query, corpus)
# match = "1psum d0l0r"
但是当差异是字符删除时,它不是.
query = "ipsum dolor"
corpus = "lorem 1psum dlr sit amet"
match = get_best_match(query, corpus)
# match = "psum dlr si"
# expected_match = "1psum dlr"
有没有办法获得更灵活的结果大小(至于expected_match)？
我现在使用的解决方案是扩展ngrams (n-k)-grams for k = {1,2,3}以防止3次删除.它比第一个版本要好得多,但在速度方面效率不高,因为我们要检查的ngrams数量超过3倍.它也是一种不可推广的解决方案.
此函数查找可变长度的最佳匹配子字符串 .
该实现将语料库视为一个长字符串,因此避免了您对空格和未分隔单词的关注.
代码摘要:
1.按大小步长扫描语料库中的匹配值,step找到最高匹配值的大致位置,pos.
2.pos通过调整子串的左/右位置,找到具有最高匹配值的附近的子串.
from difflib import SequenceMatcher
def get_best_match(query, corpus, step=4, flex=3, case_sensitive=False, verbose=False):
"""Return best matching substring of corpus.
Parameters
----------
query : str
corpus : str
step : int
Step size of first match-value scan through corpus. Can be thought of
as a sort of "scan resolution". Should not exceed length of query.
flex : int
Max. left/right substring position adjustment value. Should not
exceed length of query / 2.
Outputs
-------
output0 : str
Best matching substring.
output1 : float
Match ratio of best matching substring. 1 is perfect match.
"""
def _match(a, b):
"""Compact alias for SequenceMatcher."""
return SequenceMatcher(None, a, b).ratio()
def scan_corpus(step):
"""Return list of match values from corpus-wide scan."""
match_values = []
m = 0
while m + qlen - step <= len(corpus):
match_values.append(_match(query, corpus[m : m-1+qlen]))
if verbose:
print query, "-", corpus[m: m + qlen], _match(query, corpus[m: m + qlen])
m += step
return match_values
def index_max(v):
"""Return index of max value."""
return max(xrange(len(v)), key=v.__getitem__)
def adjust_left_right_positions():
"""Return left/right positions for best string match."""
# bp_* is synonym for 'Best Position Left/Right' and are adjusted
# to optimize bmv_*
p_l, bp_l = [pos] * 2
p_r, bp_r = [pos + qlen] * 2
# bmv_* are declared here in case they are untouched in optimization
bmv_l = match_values[p_l / step]
bmv_r = match_values[p_l / step]
for f in range(flex):
ll = _match(query, corpus[p_l - f: p_r])
if ll > bmv_l:
bmv_l = ll
bp_l = p_l - f
lr = _match(query, corpus[p_l + f: p_r])
if lr > bmv_l:
bmv_l = lr
bp_l = p_l + f
rl = _match(query, corpus[p_l: p_r - f])
if rl > bmv_r:
bmv_r = rl
bp_r = p_r - f
rr = _match(query, corpus[p_l: p_r + f])
if rr > bmv_r:
bmv_r = rr
bp_r = p_r + f
if verbose:
print "\n" + str(f)
print "ll: -- value: %f -- snippet: %s" % (ll, corpus[p_l - f: p_r])
print "lr: -- value: %f -- snippet: %s" % (lr, corpus[p_l + f: p_r])
print "rl: -- value: %f -- snippet: %s" % (rl, corpus[p_l: p_r - f])
print "rr: -- value: %f -- snippet: %s" % (rl, corpus[p_l: p_r + f])
return bp_l, bp_r, _match(query, corpus[bp_l : bp_r])
if not case_sensitive:
query = query.lower()
corpus = corpus.lower()
qlen = len(query)
if flex >= qlen/2:
print "Warning: flex exceeds length of query / 2. Setting to default."
flex = 3
match_values = scan_corpus(step)
pos = index_max(match_values) * step
pos_left, pos_right, match_value = adjust_left_right_positions()
return corpus[pos_left: pos_right].strip(), match_value
例:
query = "ipsum dolor"
corpus = "lorem i psum d0l0r sit amet"
match = get_best_match(query, corpus, step=2, flex=4)
print match
('i psum d0l0r', 0.782608695652174)
一些好的启发式建议是始终保持step < len(query) * 3/4,和flex < len(query) / 3.我还添加了区分大小写,以防这很重要.当您开始使用step和flex值时,它可以很好地工作.小步长值可以提供更好的结果,但计算时间更长.flex控制允许生成的子字符串的长度的灵活性.
重要的是要注意:这只会找到第一个最佳匹配,所以如果有多个同样好的匹配,则只返回第一个匹配.要允许多个匹配,请更改index_max()以返回n输入列表的最高值的索引列表,并循环访问adjust_left_right_positions()该列表中的值.