[1H4-GS-1c] 基礎・理論：アルゴリズム

[1H4-GS-1c-05] 最大確率分割のSuffix Arrayを用いた高速なアルゴリズム

〇梅村 恭司¹、小原 佑斗¹、吉田 光男¹ (1. 豊橋技術科学大学)

キーワード：アルゴリズム、最大確率分割、接尾辞配列

同時確率を最大化する文字列の分割を求める問題がある。本稿では、それを求める高速な方法を求めることを目的とする。確率を計算する文字列の順番を工夫し、文字列の確率を推定する場合に、その直前に求めた文字列に一文字加えるケースでは、つかの文字だけの処理を行えば良いことを利用して、文字列の長さに依存しない計算時間で確率（または頻度）を求めることができ、それによて通常の方法に比べて、計算のオーダーが向上することがわり、実際に高速に動作することが確認できた。