多字段模糊联系人匹配算法深度解析

1. 问题陈述

1.1 形式化定义

设 (\mathcal{C}) 为微信联系人集合，每个联系人 (c \in \mathcal{C}) 具有三个标识属性：

• 用户名（username）：(u(c) \in \Sigma^*)，系统唯一标识符，格式通常为 wxid_xxxxxxxx 或包含 @chatroom 后缀的群聊标识
• 显示名（display name）：(d(c) \in \Sigma^*)，用户设置的昵称
• 备注名（alias）：(a(c) \in \Sigma^* \cup {\bot})，用户为联系人设置的本地备注（可能为空）

给定查询字符串 (q \in \Sigma^*)，多字段模糊联系人匹配问题要求找到映射函数：

[f: \Sigma^* \to \mathcal{C} \cup {\text{null}}]

使得： [f(q) = \begin{cases} c & \text{if } q \approx c \ \text{null} & \text{otherwise} \end{cases}]

其中 (\approx) 表示"匹配"关系，需满足以下优先级约束（按优先级降序）：

1.2 实际场景约束

该算法运行在微信 MCP Server 的交互场景中，具有以下特点：

• 高容错需求：用户可能输入昵称、备注名的任意子串，甚至拼写变体
• 实时性要求：每次 AI 工具调用需在毫秒级完成解析
• 歧义处理：多个匹配结果时需确定性地返回最优解
• 安全边界：无法匹配时应明确返回失败，避免信息泄露

2. 直觉与关键洞察

2.1 朴素方法的失效

方法 A：纯精确匹配

def naive_exact(query, contacts):
    for c in contacts:
        if query == c.username or query == c.display_name:
            return c
    return None

• 失效原因：用户几乎不会完整输入 wxid_abc123，而是说"看看张三的消息"

方法 B：单一模糊度量

def naive_fuzzy(query, contacts):
    best_score = -inf
    best_match = None
    for c in contacts:
        score = edit_distance(query.lower(), c.display_name.lower())
        if score > best_score:
            best_score, best_match = score, c
    return best_match

• 失效原因：编辑距离对中文支持差；计算复杂度高 (O(n \cdot m \cdot |\mathcal{C}|))；过度模糊可能导致错误匹配

方法 C：简单子串匹配

def naive_substring(query, contacts):
    for c in contacts:
        if query in c.display_name:
            return c  # 返回首个匹配，非最优
    return None

• 失效原因：无优先级区分；"张"可能匹配数百个联系人；确定性差

2.2 核心洞察

该算法的有效性建立在三个关键观察上：

观察 1（身份层级性）：微信的用户名 (u(c)) 是全局唯一标识符，具有最高权威性。任何能直接识别用户名的查询都应优先处理。

观察 2（精确优先原则）：在相同匹配类型中，精确匹配应严格优先于子串匹配。即 "张三" 查询应优先匹配名为"张三"的用户，而非"张三丰"。

观察 3（贪婪截断特性）：用户输入通常是显示名的前缀或显著子串，而非随机片段。首次子串匹配即可接受，无需全局最优。

基于这些洞察，算法采用分层过滤 + 贪婪匹配策略，而非全局优化。

3. 形式化定义

3.1 匹配谓词

定义匹配谓词族 (\mathcal{P} = {P_1, P_2, P_3, P_4})：

[ \begin{aligned} P_1(q, c) &\equiv q = u(c) \ P_2(q, c) &\equiv \text{starts_with}(u(c), \texttt{"wxid_"}) \lor \text{contains}(u(c), \texttt{"@chatroom"}) \ P_3(q, c) &\equiv \text{lower}(q) = \text{lower}(d(c)) \ P_4(q, c) &\equiv \text{lower}(q) \sqsubseteq \text{lower}(d(c)) \end{aligned} ]

其中 (\sqsubseteq) 表示子串关系。

3.2 优先级偏序

定义严格偏序 (\prec) 表示匹配优先级：

[P_i \prec P_j \iff i < j]

即编号越小优先级越高。

3.3 算法目标

求解决策函数：

[\hat{c} = \arg\max_{c \in \mathcal{C}} \left{ \max_{i: P_i(q,c)} w_i \right}]

其中权重 (w_i = 4 - i)（优先级数值越小权重越大），平局时按遍历顺序打破。

等价地，可表述为首次成功匹配问题：

[\hat{c} = \text{FirstMatch}\left( \bigsqcup_{i=1}^{4} \left{ c \in \mathcal{C} : P_i(q, c) \right} \right)]

其中 (\bigsqcup) 表示按优先级排序的不交并，(\text{FirstMatch}) 返回首个非空集合的元素。

3.4 完整性约束

算法需满足：

• 确定性：相同输入始终产生相同输出（假设联系人集合不变）
• 终止性：有限步骤内必然返回结果
• 完备性：若存在 (c) 使 (P_1(q,c) \lor P_2(q,c)) 成立，则必返回非 null

4. 算法描述

4.1 高层流程

4.2 详细伪代码

\begin{algorithm}
\caption{Multi-Field Fuzzy Contact Matching}
\label{alg:mffcm}
\begin{algorithmic}[1]
\Require Query string \(q\), contact database \(\mathcal{C}\)
\Ensure Username \(u \in \Sigma^* \cup \{\text{null}\}\)

\State \(\text{names} \gets \{u(c) : c \in \mathcal{C}\}\) \Comment{预计算用户名集合}

\If{\(q \in \text{names}\)} \label{line:exact-username}
    \State \Return \(q\) \Comment{P1: 精确用户名匹配}
\ElsIf{\(\text{starts\_with}(q, \texttt{"wxid\_"})\)} \label{line:wxid-prefix}
    \State \Return \(q\) \Comment{P2: wxid 前缀启发式}
\ElsIf{\(\text{contains}(q, \texttt{"@chatroom"})\)} \label{line:chatroom}
    \State \Return \(q\) \Comment{P2: 群聊标识启发式}
\EndIf

\State \(q_{\text{low}} \gets \text{to\_lower}(q)\)

\For{\((u, d) \in \text{display\_names}(\mathcal{C})\)} \label{line:exact-loop}
    \If{\(q_{\text{low}} = \text{to\_lower}(d)\)} \Comment{P3: 精确显示名匹配}
        \State \Return \(u\)
    \EndIf
\EndFor

\For{\((u, d) \in \text{display\_names}(\mathcal{C})\)} \label{line:substring-loop}
    \If{\(q_{\text{low}} \sqsubseteq \text{to\_lower}(d)\)} \Comment{P4: 子串匹配}
        \State \Return \(u\) \Comment{贪婪返回首个匹配}
    \EndIf
\EndFor

\State \Return \(\text{null}\) \label{line:fail}

\end{algorithmic}
\end{algorithm}

4.3 状态转换图

对于单次查询，算法的状态演进：

4.4 数据结构关系

def resolve_username(chat_name):
    """将聊天名/备注名/wxid 解析为 username"""
    names = get_contact_names()  # 懒加载全局缓存

    # === Layer 1: 精确身份识别 (P1-P2) ===
    if chat_name in names or \
       chat_name.startswith('wxid_') or \
       '@chatroom' in chat_name:
        return chat_name

    # === Layer 2-3: 模糊名称匹配 (P3-P4) ===
    chat_lower = chat_name.lower()
    
    # P3: 精确大小写不敏感匹配
    for uname, display in names.items():
        if chat_lower == display.lower():
            return uname
            
    # P4: 子串匹配（贪婪首个）
    for uname, display in names.items():
        if chat_lower in display.lower():
            return uname

    return None

_contact_names_cache = None

def get_contact_names():
    global _contact_names_cache
    if _contact_names_cache is None:
        _contact_names_cache = _load_from_db()
    return _contact_names_cache

# 当前：返回首个子串匹配
if chat_lower in display.lower():
    return uname  # 可能不是"最佳"匹配

-- 需维护 FTS 虚拟表
CREATE VIRTUAL TABLE contact_fts USING fts4(username, display_name);
-- 查询
SELECT username FROM contact_fts WHERE display_name MATCH '张*';

import re
pattern = re.compile(re.escape(chat_name), re.I)
for uname, display in names.items():
    if pattern.search(display):
        return uname

# 预计算 MPHT，O(1) 查询
from perfect_hash import generate_hash
mph = generate_hash(all_display_names)
idx = mph.lookup(chat_name)  # 可能冲突