如何高效检测近5000个奇幻词汇中仅差一个相似辅音的词对？

问题说明 #

• 现有近5000个ASCII格式的奇幻词汇，示例如下：

txintoq
txiqbal
txiqfun
txiqwek
txiqyal
txiyton
txonmiq
txoqwul
txoqxik

• 定义的相似辅音集合：

zs
xj
pb
td
kg

（集合可扩展为3个及以上辅音，将根据奇幻语言发音特性调整）

• 「需修正」词对规则：两个词汇仅存在一个位置的字符属于同一相似辅音集合，其余位置字符完全相同，例如：

txindan
txintan # 仅d/t不同，属于td相似集合

xumaq
jumaq # 仅x/j不同，属于xj相似集合

dolpar
dolbar # 仅p/b不同，属于pb相似集合

• 词汇长度范围：3-10个字符

现有暴力解法的问题 #

你提供的暴力解法存在两个核心问题：

1. 效率极低：通过数组includes查找相似词的时间复杂度为O(N)，整体时间复杂度达O(N²LS²)（N为词汇总数，L为平均词长，S为相似集合平均大小），对于5000个词汇来说运算量极大。
2. 逻辑漏洞：生成相似词时直接修改了原字符数组termLetters，导致后续循环的数组被污染，生成的相似词存在错误，且未处理重复词对的问题。

暴力解法代码如下：

import fs from 'fs'

const terms = fs
  .readFileSync('term.csv', 'utf-8')
  .trim()
  .split(/\n+/)
  .map(line => {
    let [term] = line.split(',')
    return term
  })
  .filter(x => x)

const consonantSets = `
zs
xj
pb
td
kg`
  .split(/\n+/)
  .map(x => x.split(''))

function computeSimilarTerms(
  term: string,
  consonantSets: Array<Array<string>>,
) {
  const termLetters = term?.split('') ?? []
  const newTerms: Array<string> = []
  for (const consonantSet of consonantSets) {
    for (const letter of consonantSet) {
      for (const letter2 of consonantSet) {
        if (letter === letter2) {
          continue
        }

        let i = 0
        while (i < termLetters.length) {
          const termLetter = termLetters[i]
          if (termLetter === letter) {
            const newTerm = termLetters.concat()
            termLetters[i] = letter2
            newTerms.push(newTerm.join(''))
          }

          i++
        }
      }
    }
  }
  return newTerms
}

for (const term of terms) {
  const similarTerms = computeSimilarTerms(term, consonantSets)
  similarTerms.forEach(similarTerm => {
    if (terms.includes(similarTerm)) {
      console.log(term, similarTerm)
    }
  })
}

优化方案 #

方案1：基于Set的快速查找优化（适合当前二元相似集合） #

核心思路是用Set替代数组实现O(1)时间的词汇查找，同时修正相似词生成的逻辑错误，避免重复输出词对。

优化后代码：

import fs from 'fs'

// 读取并处理词汇列表
const terms = fs
  .readFileSync('term.csv', 'utf-8')
  .trim()
  .split(/\n+/)
  .map(line => line.split(',')[0])
  .filter(Boolean)

// 构建字符到相似辅音的映射
const consonantMap: Record<string, string[]> = {
  'z': ['s'],
  's': ['z'],
  'x': ['j'],
  'j': ['x'],
  'p': ['b'],
  'b': ['p'],
  't': ['d'],
  'd': ['t'],
  'k': ['g'],
  'g': ['k'],
}

// 转为Set实现O(1)查找
const termSet = new Set(terms)
// 存储已发现的词对，避免重复输出（如a-b和b-a只输出一次）
const foundPairs = new Set<string>()

for (const term of terms) {
  const chars = term.split('')
  for (let i = 0; i < chars.length; i++) {
    const currentChar = chars[i]
    const similarChars = consonantMap[currentChar]
    if (!similarChars) continue

    // 生成每个相似替换后的词汇
    for (const simChar of similarChars) {
      const newChars = [...chars] // 复制数组，避免污染原数据
      newChars[i] = simChar
      const similarTerm = newChars.join('')

      if (termSet.has(similarTerm)) {
        // 按字典序排序，确保词对唯一
        const pairKey = [term, similarTerm].sort().join('-')
        if (!foundPairs.has(pairKey)) {
          foundPairs.add(pairKey)
          console.log(`需修正: ${term} ↔ ${similarTerm}`)
        }
      }
    }
  }
}

console.log(`共发现 ${foundPairs.size} 组需修正词对`)

优化点说明：

• 查找效率从O(N)提升到O(1)，整体时间复杂度降至O(NLS)（S为每个字符的相似辅音数量，当前为1）
• 修正了原代码中数组修改的逻辑错误，使用扩展运算符复制数组
• 通过排序和Set存储避免重复输出相同词对

方案2：基于特征签名的哈希分组（支持扩展多字符相似集合） #

如果后续相似辅音集合扩展为3个及以上字符，可采用特征签名的方式，将所有仅差一个相似辅音的词汇聚集到同一分组中，再生成词对。

实现代码：

import fs from 'fs'

// 读取并处理词汇列表
const terms = fs
  .readFileSync('term.csv', 'utf-8')
  .trim()
  .split(/\n+/)
  .map(line => line.split(',')[0])
  .filter(Boolean)

// 定义相似辅音等价类集合
const equivalenceSets = [['z','s'], ['x','j'], ['p','b'], ['t','d'], ['k','g']]
// 构建字符到等价类标识的映射
const charToEquiv: Record<string, string> = {}
equivalenceSets.forEach(set => {
  const setKey = set.join('')
  set.forEach(char => {
    charToEquiv[char] = setKey
  })
})

// 按词汇长度分组，不同长度的词汇不可能符合条件
const lengthGroups = new Map<number, string[]>()
terms.forEach(term => {
  const len = term.length
  if (!lengthGroups.has(len)) lengthGroups.set(len, [])
  lengthGroups.get(len)!.push(term)
})

const foundPairs = new Set<string>()

// 遍历每个长度组
lengthGroups.forEach(groupTerms => {
  const signatureMap = new Map<string, string[]>()

  groupTerms.forEach(term => {
    const chars = term.split('')
    // 为每个位置生成特征签名：去掉当前位置的字符 + 当前位置字符的等价类
    for (let i = 0; i < chars.length; i++) {
      const prefix = chars.slice(0, i).join('')
      const suffix = chars.slice(i+1).join('')
      const equivKey = charToEquiv[chars[i]] || chars[i]
      const signature = `${prefix}_${suffix}_${equivKey}`

      if (!signatureMap.has(signature)) signatureMap.set(signature, [])
      signatureMap.get(signature)!.push(term)
    }
  })

  // 从每个特征签名的词汇列表中生成词对
  signatureMap.forEach(termsList => {
    if (termsList.length < 2) return
    // 生成所有不重复的两两组合
    for (let i = 0; i < termsList.length; i++) {
      for (let j = i + 1; j < termsList.length; j++) {
        const pairKey = [termsList[i], termsList[j]].sort().join('-')
        foundPairs.add(pairKey)
      }
    }
  })
})

// 输出结果
foundPairs.forEach(pairKey => {
  const [termA, termB] = pairKey.split('-')
  console.log(`需修正: ${termA} ↔ ${termB}`)
})

console.log(`共发现 ${foundPairs.size} 组需修正词对`)

优势说明：

• 支持任意大小的相似辅音集合，无需修改核心替换逻辑
• 仅比较同长度词汇，减少无效运算
• 特征签名的方式能高效聚集符合条件的词汇，避免冗余计算

内容的提问来源于stack exchange，提问作者Lance Pollard