Un moyen de trouver des mots qui diffèrent d'une seule consonne dans une grande liste de mots

Question

J'ai une liste de près de 5 000 mots « fantastiques » écrits en texte ASCII. Certains de ces mots sont les suivants :

txintoq
txiqbal
txiqfun
txiqwek
txiqyal
txiyton
txonmiq
txoqwul
txoqxik≪/pré>
<p>Je souhaite concevoir un algorithme qui vérifie/vérifie qu'aucun mot dans une liste ne diffère d'une seule "consonne similaire".Je vais donc définir « ensemble de consonnes similaires » comme ceci (provisoirement) : </p>
<pre class="brush:php;toolbar:false;">zs
xj
pb
td
kg≪/pré>
<p><em>Il peut y avoir 3 consonnes ou plus dans un ensemble, mais je n'en montrerai que 2 maintenant. À mesure que j’en apprends davantage sur les consonnes qui se ressemblent dans les tons des langues fantastiques, je dois affiner davantage cette définition. </em></p>
<p>Par conséquent, les mots comme ceux-ci seront marqués comme « nécessite une correction » (car ils semblent trop similaires) : </p>
<pre class="brush:php;toolbar:false;">txindan
txintan # Seul d/t est différent

xumaq
jumaq # Seul x/j est différent

dolpar
dolbar # Seul un b/p est différent

Comment puis-je trouver ces mots qui diffèrent par une seule consonne dans ma liste d'environ 5 000 mots d'une manière relativement efficace

C'est une solution très naïve que j'ai actuellement en tête, comme suit :

importer fs depuis 'fs'

termes const = fs
  .readFileSync('term.csv', 'utf-8')
  .garniture()
  .split(/n+/)
  .map(ligne => {
    laisser [terme] = line.split(',')
    délai de retour
  })
  .filter(x => x)

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

fonction calculateSimilarTerms (
  terme : chaîne,
  consonantSets : Array>,
) {
  const termLetters = term?.split('') ??
  const newTerms : Array
  pour (const consonantSet de consonantSets) {
    pour (lettre const de consonantSet) {
      pour (lettre const2 de consonantSet) {
        si (lettre === lettre2) {
          continuer
        }

        soit je = 0
        while (i < termLetters.length) {
          const termLetter = termLetters[i]
          if (termLetter === lettre) {
            const newTerm = termLetters.concat()
            termeLettres[i] = lettre2
            newTerms.push(newTerm.join(''))
          }

          je++
        }
      }
    }
  }
  retourner les nouvelles conditions
}

pour (terme const des termes) {
  const similarTerms = calculateSimilarTerms (terme, consonantSets)
  similarTerms.forEach(similarTerm => {
    if (terms.includes(similarTerm)) {
      console.log(terme, similarTerm)
    }
  })
}
Comment cela peut-il être accompli avec relativement peu de force brute ? Et cette solution est incomplète car elle ne crée pas  toutes les combinaisons de mots similaires possibles. Donc, quelque part dans l'algorithme, il devrait être capable de le faire. Des idées? 

Answer 1

Choisissez une consonne dans chaque groupe pour être le "représentant" de ce groupe. Ensuite, créez une carte qui regroupe les mots de telle sorte qu'ils deviennent identiques lorsque leurs consonnes sont remplacées par leurs consonnes représentatives.

Remarque importante : Cette méthode ne fonctionne que lorsque les groupes de consonnes forment des classes d'équivalence. En particulier, la similarité des consonnes doit être transitive. Si 'bp'相似，'bv'相似，但'pv' n’est pas similaire, cette méthode n’a aucun effet.

Voici le code de l'exemple en Python ; je vous laisse écrire le code JavaScript.

• f est une cartographie qui mappe chaque consonne à sa consonne représentative
 ;
• d est une carte qui mappe chaque mot représenté à une liste de mots avec cette représentation.

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

Enfin, nous pouvons voir quels mots sont similaires :

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