お世話になっています。さて厳密にはBPEではないと思いますが、類似のアイディアを文字列に適用したものがあります。

辞書に3つの単語があるとします（本番はもっと巨大な辞書を使います）

  • 我
  • 喜欢
  • 水果

そして次の入力を取ります。

我喜欢水果

これを1文字ずつに分解します。

我 喜 欢 水 果

隣り合う2つの文字を連結して辞書引きをします。

  • 我喜
  • 喜欢 <- in the dic
  • 欢水
  • 水果 <- in the dic

辞書にあったものは1語とみなします。これを辞書引きできなくなるまで繰り返します。1回目のループで「我 喜欢 水果」を得ました。2回目は

  • 我喜欢 水果
  • 喜欢水果

となりますが、これらは辞書にない語ですので連結せずに終わります。結果的に「我 喜欢 水果」を得ます。

これのナイーブな実装はそう難しくありませんが、ヒープを使うと効率的に圧縮できると聞きました。効率のいい実装についてご存知の方がいらっしゃいましたらご教授いただけると幸いです。あるいは参考になる情報があれば教えてください。

よろしくお願いします。