23：姓名模糊匹配优化：Levenshtein距离算法与模糊搜索

def levenshtein_distance(s1, s2):
    """计算两个字符串之间的Levenshtein距离"""
    if len(s1) < len(s2):
        return levenshtein_distance(s2, s1)
    
    # len(s1) >= len(s2)
    if len(s2) == 0:
        return len(s1)
    
    previous_row = range(len(s2) + 1)
    for i, c1 in enumerate(s1):
        current_row = [i + 1]
        for j, c2 in enumerate(s2):
            insertions = previous_row[j + 1] + 1
            deletions = current_row[j] + 1
            substitutions = previous_row[j] + (c1 != c2)
            current_row.append(min(insertions, deletions, substitutions))
        previous_row = current_row
    
    return previous_row[-1]

def optimized_levenshtein(s1, s2):
    """优化的Levenshtein距离计算"""
    # 确保s1是较长的字符串
    if len(s1) < len(s2):
        s1, s2 = s2, s1
    
    # 初始化前一行
    previous = range(len(s2) + 1)
    
    for i, c1 in enumerate(s1):
        current = [i + 1]
        for j, c2 in enumerate(s2):
            # 计算插入、删除、替换的成本
            insert = previous[j + 1] + 1
            delete = current[j] + 1
            substitute = previous[j] + (c1 != c2)
            current.append(min(insert, delete, substitute))
        previous = current
    
    return previous[-1]

def preprocess_name(name):
    """预处理姓名"""
    # 转换为小写
    name = name.lower()
    
    # 去除空格和特殊字符
    import re
    name = re.sub(r'[^a-zA-Z0-9\u4e00-\u9fa5]', '', name)
    
    # 去除常见前缀和后缀
    prefixes = ['mr', 'mrs', 'ms', 'dr', 'prof']
    suffixes = ['jr', 'sr', 'iii', 'iv']
    
    for prefix in prefixes:
        if name.startswith(prefix):
            name = name[len(prefix):]
    
    for suffix in suffixes:
        if name.endswith(suffix):
            name = name[:-len(suffix)]
    
    # 去除多余空格
    name = ' '.join(name.split())
    
    return name

def calculate_similarity(name1, name2):
    """计算两个姓名的相似度"""
    # 预处理姓名
    name1 = preprocess_name(name1)
    name2 = preprocess_name(name2)
    
    # 计算Levenshtein距离
    distance = optimized_levenshtein(name1, name2)
    
    # 计算相似度得分（0-100）
    max_length = max(len(name1), len(name2))
    if max_length == 0:
        return 100
    
    similarity = (1 - distance / max_length) * 100
    return similarity

class FuzzyNameSearch:
    def __init__(self, name_database):
        self.name_database = name_database
        self.cache = {}
    
    def search(self, query, threshold=70):
        """模糊搜索姓名"""
        # 检查缓存
        cache_key = f"{query}_{threshold}"
        if cache_key in self.cache:
            return self.cache[cache_key]
        
        # 预处理查询
        processed_query = preprocess_name(query)
        
        # 计算相似度并筛选
        results = []
        for name in self.name_database:
            similarity = calculate_similarity(processed_query, name)
            if similarity >= threshold:
                results.append((name, similarity))
        
        # 按相似度排序
        results.sort(key=lambda x: x[1], reverse=True)
        
        # 缓存结果
        self.cache[cache_key] = results
        
        return results
    
    def add_name(self, name):
        """添加姓名到数据库"""
        processed_name = preprocess_name(name)
        if processed_name not in self.name_database:
            self.name_database.append(processed_name)
            # 清空缓存
            self.cache.clear()
    
    def remove_name(self, name):
        """从数据库中移除姓名"""
        processed_name = preprocess_name(name)
        if processed_name in self.name_database:
            self.name_database.remove(processed_name)
            # 清空缓存
            self.cache.clear()

class NameIndex:
    def __init__(self):
        self.index = {}
    
    def build_index(self, names):
        """构建姓名索引"""
        for name in names:
            processed_name = preprocess_name(name)
            # 提取姓名的首字母作为索引键
            if processed_name:
                first_char = processed_name[0]
                if first_char not in self.index:
                    self.index[first_char] = []
                self.index[first_char].append(processed_name)
    
    def search(self, query, threshold=70):
        """使用索引进行搜索"""
        processed_query = preprocess_name(query)
        if not processed_query:
            return []
        
        first_char = processed_query[0]
        if first_char not in self.index:
            return []
        
        # 只搜索首字母相同的姓名
        candidate_names = self.index[first_char]
        
        results = []
        for name in candidate_names:
            similarity = calculate_similarity(processed_query, name)
            if similarity >= threshold:
                results.append((name, similarity))
        
        results.sort(key=lambda x: x[1], reverse=True)
        return results

import tensorflow as tf
from tensorflow.keras.models import Model
from tensorflow.keras.layers import Input, Embedding, LSTM, Dense, Concatenate

class NameMatchingModel:
    def __init__(self, vocab_size, embedding_dim=128, lstm_units=64):
        self.vocab_size = vocab_size
        self.embedding_dim = embedding_dim
        self.lstm_units = lstm_units
        self.model = self.build_model()
    
    def build_model(self):
        """构建姓名匹配模型"""
        # 输入层
        input1 = Input(shape=(None,))
        input2 = Input(shape=(None,))
        
        # 嵌入层
        embedding = Embedding(self.vocab_size, self.embedding_dim)
        embed1 = embedding(input1)
        embed2 = embedding(input2)
        
        # LSTM层
        lstm = LSTM(self.lstm_units, return_sequences=False)
        lstm1 = lstm(embed1)
        lstm2 = lstm(embed2)
        
        # 合并层
        merged = Concatenate()([lstm1, lstm2])
        
        # 全连接层
        dense1 = Dense(64, activation='relu')(merged)
        output = Dense(1, activation='sigmoid')(dense1)
        
        # 构建模型
        model = Model(inputs=[input1, input2], outputs=output)
        model.compile(optimizer='adam', loss='binary_crossentropy', metrics=['accuracy'])
        
        return model
    
    def train(self, X1, X2, y, epochs=10, batch_size=32):
        """训练模型"""
        self.model.fit([X1, X2], y, epochs=epochs, batch_size=batch_size, validation_split=0.2)
    
    def predict(self, X1, X2):
        """预测姓名匹配度"""
        return self.model.predict([X1, X2])