1

Python でのトライの次の実装を読みました: https://stackoverflow.com/a/11016430/2225221

そのための削除機能を作成しようとしました。基本的に、最初から問題がありました。トライから単語を削除したい場合は、サブ「単語」を持つか、別の単語の「サブ単語」にすることができます。

「del dict[key]」で削除すると、上記の 2 種類の単語も削除されます。選択した単語を適切に削除する方法について、誰かが私を助けてくれませんか（それがトライにあると仮定しましょう）

4

5 に答える 5

3

_end基本的に、トライから単語を削除するには（リンク先の回答に実装されているため）、次のようにマーカーを削除するだけです。

def remove_word(trie, word):
    current_dict = trie
    for letter in word:
        current_dict = current_dict.get(letter, None)
        if current_dict is None:
            # the trie doesn't contain this word.
            break
    else:
        del current_dict[_end]

ただし、これはトライが最小サイズであることを保証するものではないことに注意してください。単語を削除した後、どの単語にも使用されなくなった分岐が残っている可能性があります。これは、データ構造の正確性には影響しません。トライが絶対に必要以上のメモリを消費する可能性があることを意味するだけです。リーフ ノードから後方に反復し、複数の子を持つブランチが見つかるまでブランチを削除することで、これを改善できます。

編集:ここでは、不要なブランチもカリングする削除機能を実装する方法を示します。おそらくもっと効率的な方法がありますが、これで始めることができます。

def remove_word2(trie, word):
    current_dict = trie
    path = [current_dict]
    for letter in word:
        current_dict = current_dict.get(letter, None)
        path.append(current_dict)
        if current_dict is None:
            # the trie doesn't contain this word.
            break
    else:
        if not path[-1].get(_end, None):
            # the trie doesn't contain this word (but a prefix of it).
            return
        deleted_branches = []
        for current_dict, letter in zip(reversed(path[:-1]), reversed(word)):
            if len(current_dict[letter]) <= 1:
                deleted_branches.append((current_dict, letter))
            else:
                break
        if len(deleted_branches) > 0:
            del deleted_branches[-1][0][deleted_branches[-1][1]]
        del path[-1][_end]

基本的に、最初に削除しようとしている単語への「パス」を見つけてから、それを逆方向に繰り返して削除できるノードを見つけます。次に、削除可能なパスのルートを削除します (_endノードも暗黙的に削除されます)。

于 2013-03-29T18:51:22.447 に答える