スポンサーリンク

コードが書ける!数式が書ける!AAが書ける!スタンプが貼れる!

無料の匿名掲示板型SNS「このはちゃんねる

新規会員募集中!

【Python】トライ木で英文のサジェストを行う【データ構造】

245, 2019-11-16

トライ木を実装してみた

トライ木というデータ構造があります。

ハッシュテーブルの代替や自然言語処理などで使われる木構造です。
サジェストの辞書などに適しているデータ構造らしいですが、興味があったのでPythonで実装してみました。


↓のように実行するとトライ木を構築してから標準入力の読み込みを開始します。
↓はThis is a pen. That is a pig.という文字列をもとにトライ木を構築しています。
keyword >の隣にサジェスト対象の文字列を入力すると構築したトライ木からサジェストを行います。

$ 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というデータの表現方法を使っていますが、これだと省エネになるみたいです。

投稿者名です。64字以内で入力してください。

必要な場合はEメールアドレスを入力してください(全体に公開されます)。

投稿する内容です。

スポンサーリンク

スポンサーリンク

スポンサーリンク

スポンサーリンク