尋找只有一個輔音不同的單字在大型單字清單中的方法

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']]