Takashi Uemura
2018-12-14LINE Engineer
これはLINE Advent Calendar 2018の14日目の記事です。
LINEの上村です。今日は文字列です。
はじめに
トライ (trie)は文字列の集合を索引化し高速な検索を可能にするデータ構造であり、領域効率や高速性を向上させた多様なアルゴリズムが提案され種々の実装が公開されています。 IPアドレスの検索、形態素解析器における辞書からの候補の列挙、キー入力時のオートコンプリートといった有益な応用があり、文字列業界以外でもご存知の方は多いかもしれません。
この記事で紹介するsftrieは簡単で効率よい新たなトライ表現とそのC++実装です。
https://github.com/tuem/sftrie
主な特徴は以下の通りです:
大きなアルファベットをサポートします。また、いわゆるNULL文字も必要としないため、バイト列やASCIIコードからUnicode、単語等に割り振ったIDのような一般の整数まで、様々な値を文字型として扱えます
ノード探索順の工夫に基づいたトライ表現により、単純な構造ながら比較的良好な性能を実現します。日本語テキストの場合、UTF-8の代わりにUT
