Möglichkeit, in einer großen Wortliste Wörter zu finden, die sich nur um einen Konsonanten unterscheiden

Question

Ich habe eine Liste mit fast 5000 „Fantasie“-Wörtern, die in ASCII-Text geschrieben sind. Einige dieser Wörter lauten wie folgt:

txintoq
txiqbal
txiqfun
txiqwek
txiqyal
txiyton
txonmiq
txoqwul
txoqxik

Ich möchte einen Algorithmus entwerfen, der prüft/verifiziert, dass sich keine zwei Wörter in einer Liste nur durch einen „ähnlichen Konsonanten“ unterscheiden.Deshalb werde ich „Satz ähnlicher Konsonanten“ (vorläufig) wie folgt definieren:

zs
xj
pb
td
kg

Es kann 3 oder mehr Konsonanten in einem Satz geben, aber ich werde jetzt nur 2 zeigen. Da ich mehr darüber erfahre, welche Konsonanten in den Tönen von Fantasiesprachen gleich klingen, muss ich diese Definition weiter verfeinern.

Daher werden Wörter wie die folgenden als „Korrektur erforderlich“ markiert (weil sie zu ähnlich klingen):

txindan
txintan # Nur d/t ist unterschiedlich

xumaq
jumaq # Nur x/j ist unterschiedlich

Dolpar
dolbar # Nur ein b/p ist anders

Wie finde ich diese Wörter, die sich nur um einen Konsonanten in meiner Liste von ~5000 Wörtern unterscheiden, auf relativ effiziente Weise

Das ist eine sehr naive Lösung, die ich derzeit im Sinn habe, und zwar wie folgt:

fs aus 'fs' importieren

const terme = fs
  .readFileSync('term.csv', 'utf-8')
  .trimmen()
  .split(/n+/)
  .map(line => {
    let [term] = line.split(',')
    Rückgabefrist
  })
  .filter(x => x)

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

Funktion berechnenSimilarTerms(
  Begriff: Zeichenfolge,
  consonantSets: Array<Array<string>>,
) {
  const termLetters = term?.split('') ??
  const newTerms: Array<string>
  for (const consonantSet of consonantSets) {
    for (const-Buchstabe von consonantSet) {
      for (const letter2 of consonantSet) {
        if (Buchstabe === Buchstabe2) {
          weitermachen
        }

        sei i = 0
        while (i < termLetters.length) {
          const termLetter = termLetters[i]
          if (termLetter === Buchstabe) {
            const newTerm = termLetters.concat()
            termLetters[i] = Buchstabe2
            newTerms.push(newTerm.join(''))
          }

          i++
        }
      }
    }
  }
  return newTerms
}

for (const term of terms) {
  const ähnlicheTerms = berechneSimilarTerms(term, consonantSets)
  ähnlicheTerms.forEach(similarTerm => {
    if (terms.includes(similarTerm)) {
      console.log(Begriff, ähnlicher Begriff)
    }
  })
}

Wie kann dies mit relativ wenig roher Gewalt erreicht werden? Und diese Lösung ist unvollständig, da sie nicht alle möglichen ähnlichen Wortkombinationen erstellt. Irgendwo im Algorithmus sollte dies also möglich sein. Irgendwelche Ideen?

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