L'implementazione di un trie patricia per l'uso come un dizionario

Question

Sto cercando di implementare un trie patricia con i metodi addWord(), isWord(), e isPrefix() come un mezzo per memorizzare una grande dizionario di parole per il recupero rapido (tra cui la ricerca di prefisso). Ho letto su concetti ma semplicemente non stanno chiarendo in un'implementazione. Voglio sapere (in codice Java o Python) come implementare il Trie, in particolare i nodi (o dovrei implementare in modo ricorsivo). Ho visto una persona che ha implementato con una serie di 26 nodi figlio impostato su NULL / Nessuno. Esiste una strategia migliore (come ad esempio il trattamento delle lettere come bit) e come si sarebbe implementarlo?

Answer 1

Qualcun altro ha fatto una domanda su Patricia cerca qualche tempo fa e ho pensato di fare un'implementazione di Python, allora, ma questa volta ho deciso di realtà dare un colpo (sì, questo è il modo in mare, ma sembrava un bel po ' progetto). Quello che ho fatto non è forse un'implementazione trie Patricia puro, ma mi piace il mio modo migliore. Altro Patricia prova (in altre lingue) utilizzare solo una lista per i bambini e verificare ogni bambino per vedere v'è una corrispondenza, ma ho pensato che questo era piuttosto inefficiente così io uso dizionari. Qui è fondamentalmente come ho impostato in su:

inizierò al nodo radice. La radice è solo un dizionario. Il dizionario ha le chiavi che sono tutti i singoli caratteri (le prime lettere di parole) che portano alle filiali. I valori corrispondenti a ciascun tasto sono elenchi in cui il primo elemento è una stringa che dà il resto della stringa che corrisponde con questo ramo del trie, e il secondo elemento è un dizionario che porta a ulteriori rami da questo nodo. Questo dizionario ha anche tasti dei caratteri singoli che corrispondono con la prima lettera del resto della parola e il processo continua lungo il trie.

Un'altra cosa che vorrei menzionare è che se un dato nodo ha filiali, ma è anche una parola in trie per sé, quindi, che è denotato da avere una chiave '' nel dizionario che porta ad un nodo con la lista ['',{}].

Ecco un piccolo esempio che mostra come le parole sono memorizzati (il nodo radice è la _d variabile):

>>> x = patricia()
>>> x.addWord('abcabc')
>>> x._d
{'a': ['bcabc', {}]}
>>> x.addWord('abcdef')
>>> x._d
{'a': ['bc', {'a': ['bc', {}], 'd': ['ef', {}]}]}
>>> x.addWord('abc')
{'a': ['bc', {'a': ['bc', {}], '': ['', {}], 'd': ['ef', {}]}]}

Si noti che in quest'ultimo caso, un '' chiave è stato aggiunto al dizionario per denotare che 'abc' è una parola in aggiunta al 'abcdef' e 'abcabc'.

Codice Sorgente

class patricia():
    def __init__(self):
        self._data = {}

    def addWord(self, word):
        data = self._data
        i = 0
        while 1:
            try:
                node = data[word[i:i+1]]
            except KeyError:
                if data:
                    data[word[i:i+1]] = [word[i+1:],{}]
                else:
                    if word[i:i+1] == '':
                        return
                    else:
                        if i != 0:
                            data[''] = ['',{}]
                        data[word[i:i+1]] = [word[i+1:],{}]
                return

            i += 1
            if word.startswith(node[0],i):
                if len(word[i:]) == len(node[0]):
                    if node[1]:
                        try:
                            node[1]['']
                        except KeyError:
                            data = node[1]
                            data[''] = ['',{}]
                    return
                else:
                    i += len(node[0])
                    data = node[1]
            else:
                ii = i
                j = 0
                while ii != len(word) and j != len(node[0]) and \
                      word[ii:ii+1] == node[0][j:j+1]:
                    ii += 1
                    j += 1
                tmpdata = {}
                tmpdata[node[0][j:j+1]] = [node[0][j+1:],node[1]]
                tmpdata[word[ii:ii+1]] = [word[ii+1:],{}]
                data[word[i-1:i]] = [node[0][:j],tmpdata]
                return

    def isWord(self,word):
        data = self._data
        i = 0
        while 1:
            try:
                node = data[word[i:i+1]]
            except KeyError:
                return False
            i += 1
            if word.startswith(node[0],i):
                if len(word[i:]) == len(node[0]):
                    if node[1]:
                        try:
                            node[1]['']
                        except KeyError:
                            return False
                    return True
                else:
                    i += len(node[0])
                    data = node[1]
            else:
                return False

    def isPrefix(self,word):
        data = self._data
        i = 0
        wordlen = len(word)
        while 1:
            try:
                node = data[word[i:i+1]]
            except KeyError:
                return False
            i += 1
            if word.startswith(node[0][:wordlen-i],i):
                if wordlen - i > len(node[0]):
                    i += len(node[0])
                    data = node[1]
                else:
                    return True
            else:
                return False

    def removeWord(self,word):
        data = self._data
        i = 0
        while 1:
            try:
                node = data[word[i:i+1]]
            except KeyError:
                print "Word is not in trie."
                return
            i += 1
            if word.startswith(node[0],i):
                if len(word[i:]) == len(node[0]):
                    if node[1]:
                        try:
                            node[1]['']
                            node[1].pop('')
                        except KeyError:
                            print "Word is not in trie."
                        return
                    data.pop(word[i-1:i])
                    return
                else:
                    i += len(node[0])
                    data = node[1]
            else:
                print "Word is not in trie."
                return


    __getitem__ = isWord

Avrete notato che alla fine ho impostato __getitem__ al metodo isWord. Questo significa che

x['abc']

restituirà se 'abc' nel trie o meno.

Penso che forse dovrei fare un modulo da questo e lo presenta al PyPI, ma ha bisogno di ulteriori test e almeno un metodo removeWord. Se trovate qualche bug fatemi sapere, ma sembra funzionare abbastanza bene. Inoltre, se si vede tutti grandi miglioramenti in termini di efficienza Vorrei anche sentire su di loro. Ho pensato di fare qualcosa di avere dizionari vuoti in fondo a ogni ramo, ma sto lasciando per ora. Questi dizionari vuoti possono essere sostituiti con dati collegati alla parola di espandere gli usi di attuazione per esempio.

In ogni caso, se non ti piace il modo in cui ho implementato, almeno forse questo vi darà alcune idee su come si desidera implementare la propria versione.

Answer 2

Ecco un'implementazione ricorsiva utilizzando metodi più divinatorio:

def matching_prefix_index(word1, word2):
    max_len = min(len(word1),len(word2))
    for i in range(max_len):
        if word2[i] != word1[i]:
            return i
    return max_len

class PatriciaTrie(object):
    def __init__(self):
        self._storage = {}
        self._complete_prefix_flag = False

    def _find_storage_key(self, word):
        for key in self._storage:
            prefix_index = matching_prefix_index(key, word)
            if prefix_index > 0:
                return (key, prefix_index)
        return (None, None)

    def add(self, word):
        if word == '':
            self._complete_prefix_flag = True
            return True

        key, prefix_index = self._find_storage_key(word)
        if key is not None:
            if prefix_index == len(key):
                return self._storage[key].add(word[len(key):])
            else:
                new_tree = PatriciaTrie()
                new_tree._storage[key[prefix_index:]] = self._storage.pop(key)
                self._storage[key[0:prefix_index]] = new_tree
                return new_tree.add(word[prefix_index:])
        else:
            self._storage[word] = PatriciaTrie()
            self._storage[word].add('')
            return True

    def remove(self, word):
        if word == '':
            self._complete_prefix_flag = False
            return True

        key, prefix_index = self._find_storage_key(word)
        if key is None or prefix_index != len(key):
            return False

        subword = word[prefix_index:]
        subtrie = self._storage[key]
        if subtrie.remove(subword):
            if (not subtrie._complete_prefix_flag) and len(subtrie._storage) == 0:
                self._storage.pop(key)
            return True
        else:
            return False

    def __contains__(self, word):
        if word == '':
            return self._complete_prefix_flag

        key, prefix_index = self._find_storage_key(word)
        if key is None or prefix_index != len(key):
            return False
        else:
            return (word[prefix_index:] in self._storage[key])

    def has_prefix(self, word):
        if word == '':
            return True

        key, prefix_index = self._find_storage_key(word)
        if key is None:
            return False
        elif len(key) > len(word):
            return (prefix_index == len(word))
        elif len(key) != prefix_index:
            return False
        else:
            return self._storage[key].has_prefix(word[prefix_index:])