Python实现论文n-Gram/2L-approximation索引：归并外连接困惑

我正在实现Min-Soo Kim、Kyu-Young Whang与Jae-Gil Lee三人论文中的n-Gram/2L-approximation索引，索引构建过程已经完成，但卡在了查询算法的**merge outer join（归并外连接）**步骤上。

论文中对该步骤的描述：

算法通过1-sliding技术从查询串Q提取n-gram，在前端索引中查找这些n-gram的倒排列表，随后以m-subsequence标识符为连接属性，在这些倒排列表间执行归并外连接，找到满足定理1必要条件的候选m-subsequence集合{Si}。

我已经完成了部分Python代码，但不确定如何继续实现该连接步骤，希望获得相关建议或参考资料：

from math import ceil, floor

class NGramIndex:
    def __init__(self, m: int, n: int):
        self.m: int = m  # m-subsequence length
        self.n: int = n  # n-gram length
        self.backend_index = dict()
        self.frontend_index = dict()
        self.msubseq_set = []  # Set of msubsequences
        
    def append(self, doc: str, doc_id: int):
        N = len(doc)
        
        max_range = ceil(N / self.m)
        for i in range(0, max_range):
            offset = i * self.m
        
            msubseq = doc[i * self.m: i * self.m + self.m]
            # if extracted subseq is smaller, pad it with extra-char
            if len(msubseq) < self.m:
                msubseq += '$' * (self.m - len(msubseq))
            
            if msubseq not in self.backend_index:
                self.backend_index[msubseq] = [(doc_id, [offset])]
            elif self.backend_index[msubseq][-1][0] == doc_id:
                self.backend_index[msubseq][-1][1].append(offset)
            else:
                self.backend_index[msubseq].append((doc_id, [offset]))
                
            if msubseq in self.msubseq_set:
                # subseq_id is the unique identifier in msubseq_set
                subseq_id = self.msubseq_set.index(msubseq)
            else:
                self.msubseq_set.append(msubseq)
                subseq_id = len(self.msubseq_set) - 1
                max_q_range = self.m - self.n + 1

                for ngram_offset in range(0, max_q_range):
                    ngram = msubseq[ngram_offset:ngram_offset + self.n]
                    if ngram not in self.frontend_index:
                        self.frontend_index[ngram] = [(subseq_id, [ngram_offset])]
                    elif self.frontend_index[ngram][-1][0] == subseq_id:
                        self.frontend_index[ngram][-1][1].append(ngram_offset)
                    else:
                        self.frontend_index[ngram].append((subseq_id, [ngram_offset]))
                        
    def query(self, query_word: str, k: int):
        """
        Query the index for results
        k = error tolerance (threshold)
        
        """
        t = floor((len(query_word) + 1) / self.m) - 1
        eps = floor(k / t)
        # r is used for filtration later
        r = (self.m - self.n + 1) - (eps * self.n)
        
        postings = []
        
        for i in range(0, len(query_word) - self.n + 1):
            ngram = query_word[i: i + self.n]
            if ngram in self.frontend_index:
                postings.append(self.frontend_index[ngram])
        
        # TODO: Perform merge outer join?

实现归并外连接的建议 #

1. 明确核心逻辑

这里的归并外连接是以subseq_id为键，合并所有倒排列表中相同subseq_id的条目，同时保留所有出现过的subseq_id（即使只在部分列表中出现）。由于倒排列表本身是按subseq_id递增有序的（构建时按msubseq_set的加入顺序生成），可以用多路归并的方式高效处理。

2. 归并外连接的代码实现

在query方法的TODO位置添加以下逻辑：

# 实现多路归并外连接
if not postings:
    return []

# 确保每个posting列表按subseq_id有序（构建时已保证，这里做二次确认）
sorted_postings = [sorted(post, key=lambda x: x[0]) for post in postings]
# 初始化每个列表的指针
pointers = [0] * len(sorted_postings)
candidates = {}

while True:
    # 收集所有当前指针有效的subseq_id
    current_ids = []
    for idx, ptr in enumerate(pointers):
        if ptr < len(sorted_postings[idx]):
            current_ids.append((sorted_postings[idx][ptr][0], idx))
    
    if not current_ids:
        break
    
    # 找到当前最小的subseq_id
    current_ids.sort()
    min_subseq_id = current_ids[0][0]
    
    # 收集该subseq_id对应的所有ngram偏移
    merged_offsets = set()
    for subseq_id, post_idx in current_ids:
        if subseq_id != min_subseq_id:
            break
        # 合并当前条目的偏移列表
        merged_offsets.update(sorted_postings[post_idx][pointers[post_idx]][1])
        # 移动对应列表的指针
        pointers[post_idx] += 1
    
    # 记录候选subseq_id的匹配偏移
    candidates[min_subseq_id] = merged_offsets

# 根据定理1的条件过滤候选：匹配的ngram数量≥r
valid_subseq_ids = [sid for sid, offsets in candidates.items() if len(offsets) >= r]
# 转换为对应的m-subsequence
valid_msubseqs = [(sid, self.msubseq_set[sid]) for sid in valid_subseq_ids]

return valid_msubseqs

3. 关键细节说明

• 匹配计数：代码中用set去重偏移量，统计该subseq_id与查询n-gram匹配的不同位置数量，这符合论文中定理1对匹配数量的要求。
• 效率：多路归并的时间复杂度为O(total_entries)，其中total_entries是所有倒排列表的总条目数，避免了低效的全量笛卡尔积操作。
• 后续扩展：得到有效候选后，可以进一步关联backend_index获取对应的文档ID和偏移信息，完成最终的查询结果返回。

参考方向

可以查阅多路归并算法的实现细节，以及数据库中外连接的核心逻辑，这类资料能帮助你理解归并外连接的底层原理，灵活调整实现细节以贴合论文要求。

内容的提问来源于stack exchange，提问作者Lukáš Moravec