Cara untuk mencari perkataan yang berbeza dengan hanya satu konsonan dalam senarai perkataan yang besar

Question

Saya mempunyai senarai hampir 5000 perkataan "fantasi" yang ditulis dalam teks ASCII. Beberapa perkataan ini adalah seperti berikut:

txintoq
txiqbal
txiqfun
txiqwek
txiqyal
txiyton
txonmiq
txoqwul
txoqxik

Saya mahu mereka bentuk algoritma yang menyemak/mengesahkan bahawa tiada dua perkataan dalam senarai berbeza dengan hanya satu "konsonan serupa".Jadi saya akan mentakrifkan "set konsonan serupa" seperti ini (secara sementara):

zs
xj
pb
td
kg</pra>
<p><em>Mungkin terdapat 3 atau lebih konsonan dalam satu set, tetapi saya hanya akan menunjukkan 2 sekarang. Semasa saya mengetahui lebih lanjut tentang konsonan yang sama bunyinya dalam nada bahasa fantasi, saya perlu memperhalusi lagi takrifan ini. </em></p>
<p>Oleh itu, perkataan seperti berikut akan ditandakan sebagai "memerlukan pembetulan" (kerana bunyinya terlalu serupa): </p>
<pre class="brush:php;toolbar:false;">txindan
txintan # Hanya d/t berbeza

xumaq
jumaq # Hanya x/j yang berbeza

dolpar
dolbar # Hanya b/p berbeza

Bagaimanakah saya mencari perkataan ini yang berbeza dengan hanya satu konsonan dalam senarai ~5000 perkataan saya dalam cara agak cekap

Ini adalah penyelesaian yang sangat naif yang saya fikirkan pada masa ini, seperti berikut:

import fs daripada 'fs'

istilah const = fs
  .readFileSync('term.csv', 'utf-8')
  .trim()
  .split(/n+/)
  .peta(garis => {
    biarkan [istilah] = line.split(',')
    tempoh pulangan
  })
  .filter(x => x)

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

function computeSimilarTerms(
  istilah: rentetan,
  ConsonantSets: Array<Array<string>>,
) {
  const termLetters = istilah?.split('') ??
  const newSyarat: Array<rentetan>
  untuk (konsonan konsonanSet of consonantSets) {
    untuk (huruf const of consonantSet) {
      for (const letter2 of consonantSet) {
        jika (huruf === huruf2) {
          teruskan
        }

        biarkan i = 0
        manakala (i < termLetters.length) {
          const termLetter = termLetters[i]
          if (istilahSurat === huruf) {
            const newTerm = termLetters.concat()
            istilahHuruf[i] = huruf2
            newTerms.push(newTerm.join(''))
          }

          i++
        }
      }
    }
  }
  kembali Syarat baharu
}

untuk (istilah const) {
  const similarTerms = computeSimilarTerms(istilah, consonantSets)
  similarTerms.forEach(similarTerm => {
    if (terms.includes(similarTerm)) {
      console.log(istilah, similarTerm)
    }
  })
}

Bagaimana ini boleh dicapai dengan kekerasan yang agak sedikit? Dan penyelesaian ini tidak lengkap kerana ia tidak membina semua kemungkinan gabungan perkataan serupa. Jadi di suatu tempat dalam algoritma ia sepatutnya dapat melakukan ini. Ada idea?

Answer 1

Pilih konsonan dalam setiap kumpulan untuk menjadi "wakil" kumpulan tersebut. Kemudian, bina peta yang mengumpulkan kata-kata supaya ia menjadi serupa apabila konsonan mereka digantikan dengan konsonan wakil mereka.

Nota penting: Kaedah ini hanya berfungsi apabila kumpulan konsonan membentuk kelas kesetaraan. Khususnya, persamaan konsonan mestilah transitif. Jika 'bp'相似，'bv'相似，但'pv' tidak serupa, kaedah ini tidak memberi kesan.

Berikut ialah kod untuk contoh dalam Python saya membenarkan anda menulis kod JavaScript.

• f ialah pemetaan yang memetakan setiap konsonan kepada konsonan perwakilannya
• d ialah peta yang memetakan setiap perkataan yang diwakili kepada senarai perkataan dengan perwakilan ini.

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

Akhir sekali, kita dapat melihat perkataan mana yang serupa:

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