【Python】トライ木で英文のサジェストを行う【データ構造】
245, 2019-11-16
トライ木を実装してみた
トライ木というデータ構造があります。
ハッシュテーブルの代替や自然言語処理などで使われる木構造です。
サジェストの辞書などに適しているデータ構造らしいですが、興味があったのでPythonで実装してみました。
↓のように実行するとトライ木を構築してから標準入力の読み込みを開始します。
↓はThis is a pen. That is a pig.という文字列をもとにトライ木を構築しています。
keyword >の隣にサジェスト対象の文字列を入力すると構築したトライ木からサジェストを行います。
:::bash
$ python suggest.py
""
_"T"
__"h"
___"i"
____"s" This
___"a"
____"t" That
_"i"
__"s" is
_"a" a
_"p"
__"e"
___"n" pen
__"i"
___"g" pig
keyword > Th
['This', 'That']
keyword > p
['pen', 'pig']
keyword > pi
['pig']
keyword >
今回の実装では木の葉や節に値として単語を保存していますが、聞いた話によるとこの実装だと入力が多くなるとメモリ使用量が馬鹿にならないらしいです。
↑の記事ではLOUDSというデータの表現方法を使っていますが、これだと省エネになるみたいです。