シンプルで強いFrontCoding文字列辞書を紹介したい

本記事では、文字列集合を保存し検索するためのシンプルで強いデータ構造であるFrontCoding文字列辞書（以下、FC辞書）を紹介します。このために使われるデータ構造としてはハッシュ表やTrieがメジャーです。それに対して、FC辞書はあまり使われていない印象で、実際に公開されているライブラリも少ないです。

しかし、FC辞書もハッシュ表やTrieに負けない利点を備えたデータ構造ですので、用途やデータセットによっては効率的に文字列辞書を実現することができます。例えば、SIGIR 2020でのクエリ補完に関する論文 [1] では、伝統的なTrie辞書よりもFC辞書の方が高速に検索できることを示しています。また、DB圧縮などで使われるDictionary Encoding (or Domain Encoding)1 でもFC辞書は有益です [2,3]。そのため、FC辞書について知っておくと、文字列データを扱うときに幸せになれるかもしれません。

以降では、[2] の論文の内容を参考にFC辞書を解説します。

FrontCoding

まず基礎となる文字列圧縮技法であるFrontCodingについて解説します。FrontCodingとは整列済み文字列リストに対する差分圧縮技法で、直前の文字列との最長共通接頭辞（Longest Common Prefix, LCP）を削って、代わりにその長さを記述します。

例えば以下の9つの整列済み文字列をFrontCodingで圧縮すると、LCP-LenとSuffixがその結果です。便宜上、最小の文字「#」を終端文字として各文字列に追加しています。

ID String LCP-Len Suffix
0 idea# - idea#
1 ideal# 4 l#
2 ideology# 3 ology#
3 tea# 0 tea#
4 techie# 2 chie#
5 technology# 4 nology#
6 tie# 1 ie#
7 trial# 1 rial#
8 trie# 3 e#

「ideal#」は直前の文字列「idea#」と先頭4文字が共通しているので、その長さ4と残りの接尾辞「l#」にエンコードされます。「ideology#」も同様に直前の文字列「ideal#」と先頭3文字が共通しているので、その長さ3と残りの接尾辞「ology#」にエンコードされます。文字列の復元は、直前の文字列を使って逆の操作で行えます。

FrontCodingはシンプルな圧縮スキームながら、自然言語やURLなどの似たような接頭辞を持つ文字列データを効率的に圧縮することができます。

FC辞書

文字列集合 $ \{ s_0, s_1, \ldots, s_{n-1} \} $ に対して以下の操作を提供するFC辞書を考えます。

  • $ Locate(q) $：$ q = s_i $ である ID $ i $ を返す。無い場合は $ -1 $ を返す。
  • $ Decode(i) $：文字列 $ s_i $ を復元する。
  • $ Predict(q) $：文字列 $ q $ を接頭辞に持つ $ s_i $ を全て列挙する。

FrontCodingでは $ s_i $ を復元するために $ s_{i-1} $ を知っておく必要があり、$ s_0 $ から順に復元する必要があります。そこでFC辞書では、$ s_0, s_1, \ldots, s_{n-1} $ を $ k $ 個ずつのバケットに分割し、各バケットの先頭の文字列 $ s_0, s_{k}, s_{2k}, \ldots $ をエンコードせずに保存しておきます。これにより、$ s_i $ の復元はそのバケットの先頭から開始できます。以降では、バケットの先頭文字列をヘッダー文字列、残りをインナー文字列と呼びます。

例えば、前に提示した例を $ k=4 $ でバケットに分割した場合は以下のようになります。

ID String LCP-Len Suffix
0 idea# - idea#
1 ideal# 4 l#
2 ideology# 3 ology#
3 tea# 0 tea#
4 techie# - techie#
5 technology# 4 nology#
6 tie# 1 ie#
7 trial# 1 rial#
8 trie# - trie#

ヘッダー文字列 $ s_0, s_4, s_8 $ をエンコードせずに保存しています。例えば $ s_5 $ を復元するとき、そのバケットのヘッダー文字列 $ s_4 $ から復元を開始できます。

検索

$ s_i $ は整列して保存されているため、$ Locate(q) $ は以下の2ステップで実行できます。

  1. ヘッダー文字列を二分探索し、$ q $ が含まれてるかもしれないバケットを探索する。
  2. バケット内の文字列を復元し、$ q $ を探索する。

$ Predict(q) $ も $ q $ を接頭辞に持つ $ s_i $ は連続しているので同様の手順で実行できます。まず $ q $ を接頭辞に持つ最初の文字列を $ Locate $ の要領で探索し、次に$ q $ を接頭辞に持たない文字列を見つけるまで復元します。

実装

LCP-LenとSuffixを交互に並べバイト列にシリアライズし、各バケットの先頭位置を別の配列に保存しておくことで簡単に実装できます。このとき、LCP-LenはVByteのような接頭辞符号を用いて記述することで、LCP-LenとSuffixの境界が表現できます。

index: 0 20 44
bytes: idea#4l#3ology#0tea# techie#4nology#1ie#1rial# trie#
index: 0 1 2
pointers: 0 20 44

利点

  • シンプルな実装：上記した通り、FC辞書は単純なバイト列とポインタ列を用いて実装できます。Trieのように木のトポロジを表現する必要もなく、管理するポインタも高々 $ n / k $ 個で済みます。
  • キャッシュフレンドリ：FC辞書の検索では一度バケットを特定すれば後はデータを復元するだけです。そのときデータはメモリ上で隣り合っておりキャッシュ効率が良いです。Trieではポインタを使って木を走査する必要があることを考えると、その嬉しさがわかりやすいと思います。2
  • 高い圧縮率：FrontCodingでは自然言語やURLのような似たような接頭辞を持つ文字列データを効率的に圧縮することができます。また、各バケットは先頭からシーケンシャルに読み込まれるだけですので、任意の文字列圧縮アルゴリズムが適用して更に圧縮できます。具体的には後述します。

欠点

  • 二分探索が必要：ハッシュ表やTrieと比べての一番の欠点は、$ Locate $ や $ Predict $ でヘッダーに対する二分探索が必要な点です。ハッシュ表やTrieが $ O(|q|) $ 時間で $ Locate(q) $ を実行できるのに対し、FC辞書では $ O( |q| \log (n/k) ) $ 時間を必要とします。
  • Common Prefix Searchが苦手：クエリ $ q $ の接頭辞であるような $ s_i $ を列挙する操作をCommon Prefix Searchと言います。形態素解析などで必要とされ、Trieが得意とする操作ですが、FC辞書では上手く解くことができません。

Locateの高速化

$ Locate(q) $ では二分探索でバケットを特定した後、$ q = s_i $ となる文字列を見つけるまで $ s_i $ を復元し比較を繰り返すことで実行されます。このとき、一つ一つ陽に復元し文字を比較しなくても、以下のように場合分けをすることで探索を高速化できます。

現在 $ s_i $ を既に復元しており、$ \ell = lcp(q, s_i) $ を知っているとします。ここで、$ lcp $ は2つの文字列の最長共通接頭辞長です。つまり、$ q[0..\ell - 1] = s_i[0..\ell - 1] $ で $ q[\ell] \neq s_i[\ell] $ です。$ m = lcp(s_i, s_{i+1}) $ であるような $ s_{i+1} $ を復元するとき、以下の3つの場合を考えることで $ Locate $ を実行できます。

  • $ m > \ell $ の場合、$ q[\ell] \neq s_{i+1}[\ell] $ で $ s_i $ と同じ文字で不一致していることがわかるので、$ s_{i+1} $ の復元と比較はスキップできます。
  • $ m < \ell $ の場合、$ q[0 .. m - 1] = s_i[0 .. m - 1] = s_{i+1}[0 .. m - 1] $ で $ q[m] = s_{i}[m] < s_{i+1}[m] $ なので、$ s_i < q < s_{i+1} $ ということがわかり、$ q $ が辞書に含まれていないことがわかります。
  • $ m = \ell $ の場合、$ s_{i+1} $ を陽に復元して $ \ell = lcp(q, s_{i+1}) $ を更新します。$ q[\ell] < s_{i+1}[\ell] $ なら $ s_i < q < s_{i+1} $ ということがわかり、$ q $ が辞書に含まれていないことがわかります。

FC辞書の圧縮

FC辞書のバケットは先頭から読み込まれるだけですので、各バケットのバイト列は任意の文字列圧縮技法を適用して素直に圧縮することができます。ただしヘッダー文字列は二分探索に使うので、復元が遅いと検索速度に大きく影響します。そのため [2] の論文では、インナー文字列とヘッダー文字列をそれぞれ別の技法で圧縮しています。

インナー文字列（エンコードされたLCP-Lenも含む）は、ただ先頭から読み込まれる文字列ですので、圧縮率が高く且つ復元の速い技法が好ましいです。[2] ではハフマン符号とRePair圧縮を試しており、多くの場合でRePairが高い圧縮率を記録しています。

ヘッダー文字列は、二分探索ができるようにHu-Tucker符号により圧縮を試みています。Hu-Tucker符号とはハフマン符号に似た技法で、符号同士の順序が元の順序を保持するようにデータを圧縮します。そのため、クエリ $ q $ も同じようにHu-Tucker符号化することで、符号同士の比較によりヘッダー文字列を復元することなくを二分探索することができます。しかし、ヘッダー文字列の数はインナー文字列の $ 1/(k - 1) $ しかなく、インナー文字列の圧縮ほど大きな効果はありません。

Rustライブラリ

最近、FC辞書をRustで実装しました。

github.com

現在のところバイト列の圧縮はしておらず、[2] で提案されているPFC (Plain Front Coding)と同等のデータ構造を採用しています。簡単な実装ではありますが、[2] の実験結果に見られるように非常に高速な $ Decode $ と $ Predict $ を提供します。$ Locate $ は [4] の実験結果を参考にする限り、ダブル配列の2~3倍程度低速なようです。ただし $ Decode $ は2~3倍高速で、使用メモリも最大で2.4倍ほど小さいようです。

利用例

以下のように、辞書式順に文字列をビルダークラスに追加することで辞書が構築できます。 $ Locate $ などの操作も FcLocater などのクラスを通して実行できます。

use fcsd::Set;

// Input string keys should be sorted and unique.
let keys = ["ICDM", "ICML", "SIGIR", "SIGKDD", "SIGMOD"];

// Builds an indexed set.
let set = Set::new(keys).unwrap();
assert_eq!(set.len(), keys.len());

// Gets indexes associated with given keys.
let mut locator = set.locator();
assert_eq!(locator.run(b"ICML"), Some(1));
assert_eq!(locator.run(b"SIGMOD"), Some(4));
assert_eq!(locator.run(b"SIGSPATIAL"), None);

// Decodes string keys from given indexes.
let mut decoder = set.decoder();
assert_eq!(decoder.run(0), b"ICDM".to_vec());
assert_eq!(decoder.run(3), b"SIGKDD".to_vec());

// Enumerates indexes and keys stored in the set.
let mut iter = set.iter();
assert_eq!(iter.next(), Some((0, b"ICDM".to_vec())));
assert_eq!(iter.next(), Some((1, b"ICML".to_vec())));
assert_eq!(iter.next(), Some((2, b"SIGIR".to_vec())));
assert_eq!(iter.next(), Some((3, b"SIGKDD".to_vec())));
assert_eq!(iter.next(), Some((4, b"SIGMOD".to_vec())));
assert_eq!(iter.next(), None);

// Enumerates indexes and keys starting with a prefix.
let mut iter = set.predictive_iter(b"SIG");
assert_eq!(iter.next(), Some((2, b"SIGIR".to_vec())));
assert_eq!(iter.next(), Some((3, b"SIGKDD".to_vec())));
assert_eq!(iter.next(), Some((4, b"SIGMOD".to_vec())));
assert_eq!(iter.next(), None);

// Serialization / Deserialization
let mut data = Vec::<u8>::new();
set.serialize_into(&mut data).unwrap();
assert_eq!(data.len(), set.size_in_bytes());
let other = Set::deserialize_from(&data[..]).unwrap();
assert_eq!(data.len(), other.size_in_bytes());

おわりに

FC辞書は高速な $ Decode $ と $ Predict $ を要求する用途において優れたデータ構造ですので、よければ使ってみてください。

参考文献

  1. S Gog, GE Pibiri, and R Venturini. Efficient and effective query auto-completion. In SIGIR, pp 2271-2280, 2020. pdf
  2. MA Martínez-Prieto, N Brisaboa, R Cánovas, F Claude, and G Navarro. Practical compressed string dictionaries. Information Systems, 56:73–108, 2016. pdf
  3. I Müller, C Ratsch, and F Faerber. Adaptive string dictionary compression in in-memory column-store database systems, In EDBT, pp 283-294, 2014. pdf
  4. S Kanda, K Morita, and M Fuketa. Compressed double-array tries for string dictionaries supporting fast lookup. Knowledge and Information Systems, 51(3): 1023–1042, 2017. pdf
  1. 辞書を使って文字列などの可変長データを単純な固定長の整数値に置き換える技法です。固定長データは配列に保存しやすかったり比較が高速であったりと様々な利点を持つので、文字列データを扱う多くの用途でDictionary Encodingは有益です。↩
  2. ただしFC辞書は二分探索が必要なので、一概にキャッシュフレンドリと言えるわけではありません。↩