寻找只有一个辅音不同的单词在大型单词列表中的方法

Question

我有一个近5000个“幻想”单词的列表，这些单词以ASCII文本形式书写。其中一些单词如下：

txintoq
txiqbal
txiqfun
txiqwek
txiqyal
txiyton
txonmiq
txoqwul
txoqxik

我想设计一个算法，检查/验证列表中没有两个单词之间只相差一个“相似辅音”。因此，我会像这样定义“相似辅音集合”（暂时）：

zs
xj
pb
td
kg

一个集合中可能有3个或更多辅音，但我现在只展示2个。随着我对幻想语言音调中哪些辅音听起来相似的了解越来越深入，我需要进一步调整这个定义。

因此，像下面这样的单词将被标记为“需要修正”（因为它们听起来太相似）：

txindan
txintan # 只有d/t不同

xumaq
jumaq # 只有x/j不同

dolpar
dolbar # 只有a b/p不同

我如何在我的约5000个单词列表中以相对高效的方式找到这些只相差一个辅音的单词？

这是我目前所想到的一种非常天真的解决方法，如下所示：

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)
    }
  })
}

如何以相对较少的蛮力方式完成这个任务？而且这个解决方法还不完整，因为它没有构建所有可能相似的单词组合。所以在算法的某个地方，它应该能够做到这一点。有什么想法吗？

Answer 1

在每个组中选择一个辅音作为该组的“代表”。然后，构建一个将单词分组在一起的映射，当它们的辅音被代表辅音替换时，它们变得相同。

重要提示：此方法仅在辅音组形成等价类时有效。特别是，辅音的相似性必须是传递的。如果'bp'相似，'bv'相似，但'pv'不相似，则此方法无效。

以下是用Python示例的代码; 我让你编写JavaScript代码。

• f是一个将每个辅音映射到其代表辅音的映射；
• d是一个将每个代表单词映射到具有此代表的单词列表的映射。

bigwordlist = '''dolbar
dolpar
jumaq
txindan
txintan
txintoq
txiqbal
txiqfun
txiqwek
txiqyal
txinton
txonmiq
txoqwul
txoqxik
xumaq'''.splitlines()

consonant_groups = '''zs
xj
pb
td
kg'''.splitlines()

f = {}
for g in consonant_groups:
    for c in g:
        f[c] = g[0]

print(f)
# {'z': 'z', 's': 'z', 'x': 'x', 'j': 'x', 'p': 'p', 'b': 'p', 't': 't', 'd': 't', 'k': 'k', 'g': 'k'}
    
d = {}
for word in bigwordlist:
    key = ''.join(f.get(c, c) for c in word)
    d.setdefault(key, []).append(word)

print(d)
# {'tolpar': ['dolbar', 'dolpar'], 'xumaq': ['jumaq', 'xumaq'], 'txintan': ['txindan', 'txintan'], 'txintoq': ['txintoq'], 'txiqpal': ['txiqbal'], 'txiqfun': ['txiqfun'], 'txiqwek': ['txiqwek'], 'txiqyal': ['txiqyal'], 'txinton': ['txinton'], 'txonmiq': ['txonmiq'], 'txoqwul': ['txoqwul'], 'txoqxik': ['txoqxik']}

最后，我们可以看到哪些单词是相似的：

print([g for g in d.values() if len(g) > 1])
# [['dolbar', 'dolpar'], ['jumaq', 'xumaq'], ['txindan', 'txintan']]