Bagaimana untuk menggunakan pokok kamus untuk pemadanan teks dalam Python?

1. Apakah pokok kamus?

Pokok kamus (Trie), juga dipanggil pokok awalan (Prefix Tree), ialah struktur data berbentuk pokok. Pokok kamus boleh melakukan operasi carian, sisipan dan pemadaman yang cekap pada rentetan. Idea teras ialah menggunakan awalan biasa rentetan untuk mengurangkan kerumitan masa pertanyaan.

Dalam pepohon kamus, setiap nod mewakili awalan rentetan. Laluan dari nod akar ke nod daun mewakili rentetan lengkap. Setiap nod pada laluan mempunyai bendera yang menunjukkan sama ada rentetan yang diwakili oleh nod itu wujud dalam pepohon kamus.

2. Pelaksanaan pepohon kamus

Dalam Python, anda boleh menggunakan kamus (dikt) untuk melaksanakan pepohon kamus. Dalam pepohon kamus, setiap nod ialah kamus yang digunakan untuk menyimpan aksara seterusnya dan nod yang sepadan dengannya. Apabila anda perlu melintasi pepohon kamus, anda hanya perlu mencari nod yang sepadan berdasarkan aksara semasa, dan kemudian masukkan nod yang sepadan dengan aksara seterusnya, dan seterusnya sehingga rentetan tamat atau tidak dapat dipadankan.

Berikut ialah pelaksanaan pokok kamus yang mudah:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        curr = self.root
        for ch in word:
            if ch not in curr.children:
                curr.children[ch] = TrieNode()
            curr = curr.children[ch]
        curr.is_word = True

    def search(self, word):
        curr = self.root
        for ch in word:
            if ch not in curr.children:
                return False
            curr = curr.children[ch]
        return curr.is_word

    def starts_with(self, prefix):
        curr = self.root
        for ch in prefix:
            if ch not in curr.children:
                return False
            curr = curr.children[ch]
        return True

3 Aplikasi pepohon kamus

Pokok kamus boleh digunakan untuk pemadanan teks, seperti semakan ejaan perkataan, perkataan. padanan, dsb. Berikut ialah contoh mudah menggunakan pokok kamus untuk melaksanakan semakan ejaan perkataan:

import re

word_list = ['hello', 'world', 'python', 'teacher', 'student']

def sanitize_word(word):
    return re.sub(r'[^a-z]', '', word.lower())

def spell_check(word):
    trie = Trie()
    for w in word_list:
        trie.insert(sanitize_word(w))

    if trie.search(sanitize_word(word)):
        print('Correct spelling!')
    else:
        print('Did you mean one of the following words?')
        similar_words = get_similar_words(trie, sanitize_word(word))
        for w in similar_words:
            print(w)

def get_similar_words(trie, word, distance=1):
    similar_words = []
    for i in range(len(word)):
        for ch in range(ord('a'), ord('z')+1):
            new_word = word[:i] + chr(ch) + word[i+1:]
            if trie.search(new_word):
                similar_words.append(new_word)
    return similar_words

spell_check('helo')

Dalam kod di atas, kita boleh menyemak sama ada perkataan wujud dalam senarai perkataan melalui pepohon kamus. Jika perkataan itu wujud, keluarkan "Ejaan yang betul!" jika tidak, keluarkan perkataan yang serupa.

4. Ringkasan

Pokok kamus ialah struktur data yang sangat praktikal yang boleh digunakan untuk pemadanan teks yang cekap. Anda boleh menggunakan kamus untuk melaksanakan pepohon kamus dalam Python, yang sangat mudah dan mudah difahami. Dalam aplikasi praktikal, ia boleh diselaraskan dan dikembangkan mengikut keperluan sebenar untuk mencapai hasil yang lebih baik.

Atas ialah kandungan terperinci Bagaimana untuk menggunakan pokok kamus untuk pemadanan teks dalam Python?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!