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