基于词典的n-gram fuzzy matching 匹配结果的原生顺序保持方案
顺序错乱的核心根因
- n-gram生成逻辑的遍历顺序脱离原文流:现有实现是先枚举全量1-gram、再枚举全量2-gram、3-gram、4-gram,扫描顺序完全不是从原字符串的最左位置向最右位置推进,收集到的匹配结果天然不满足原始顺序
- 去重逻辑使用set结构:Python的set基于哈希表实现,本身不保留元素插入顺序,会进一步打乱结果排列
- 匹配逻辑缺失长单元优先规则:多词短语的匹配会被拆成零散单字匹配,既造成重复结果,也容易打乱位置映射
修复实现逻辑
核心思路
给每一个命中的匹配项绑定它在原字符串里的起始字符坐标,最终按照坐标从小到大排序得到顺序正确的结果,同时通过长窗口优先匹配的规则减少重复命中。
具体步骤
- 预处理原字符串:记录每个分词在原文中的起始索引,作为所有匹配项的位置锚点
- 调整扫描逻辑:从左到右滑动窗口,从允许的最大n-gram长度(当前为4)向最小长度逐次缩小窗口做匹配,一旦命中就跳过该窗口覆盖的所有分词位置,避免重复匹配
- 绑定位置存储:不管是模糊匹配的词典结果,还是正则识别的数字,命中后都以
(起始位置, 输出值)的元组形式存入临时记录列表 - 保序去重:所有扫描完成后,先按起始位置对记录列表做升序排序,再遍历列表做去重,仅保留每个值最早出现的条目,全程不使用set直接转换全量结果
核心可运行代码片段
import re from fuzzywuzzy import FuzzyDict original_str = "Hello everybody, today we have 2.000 cell phones here" max_ngram_len = 4 # 预处理:获取每个分词在原文的起始位置,作为位置锚点 word_positions = [] current_cursor = 0 for word in original_str.split(): start_pos = original_str.find(word, current_cursor) word_positions.append((start_pos, word)) current_cursor = start_pos + len(word) # 初始化模糊匹配词典 my_dict = { "brand": "ITEM_01", "model": "ITEM_02", "cell phone": "ITEM_04", "today": "ITEM_05" } fuzzy_dict = FuzzyDict(my_dict) match_records = [] scan_cursor = 0 # 从左到右逐位置扫描 while scan_cursor < len(word_positions): is_matched = False # 从最长窗口到最短窗口遍历,实现长匹配优先 for window_size in range(max_ngram_len, 0, -1): # 窗口超出分词边界直接跳过 if scan_cursor + window_size > len(word_positions): continue window_words = [word_positions[scan_cursor + offset][1] for offset in range(window_size)] window_text = " ".join(window_words) window_pos = word_positions[scan_cursor][0] # 模糊匹配词典 try: match_val = fuzzy_dict[window_text] match_records.append((window_pos, match_val)) scan_cursor += window_size is_matched = True break except: pass # 单字窗口下做数字匹配 if window_size == 1: num_pattern = r'(?:[+-]|\()?\$?\d+(?:,\d+)*(?:\.\d+)?\)?' if re.fullmatch(num_pattern, window_text): match_records.append((window_pos, window_text)) scan_cursor += 1 is_matched = True break # 无匹配则向后移动一个分词位置 if not is_matched: scan_cursor += 1 # 按位置排序 + 保序去重 match_records.sort(key=lambda item: item[0]) final_result = [] seen_vals = set() for pos, val in match_records: if val not in seen_vals: seen_vals.add(val) final_result.append(val) # 最终输出为: ['ITEM_05', '2.000', 'ITEM_04'] print(final_result)
内容的提问来源于stack exchange,提问作者Kelly o'Brian
相关产品推荐
相关产品推荐

