文字列(単語列)を解析する際、i番目の文字はその直前(N-1)文字のみ依存するというマルコフ情報源を仮定することはいろいろな場面で現れます。 例えば音声認識とか機械翻訳では、次の単語を直前(N-1)単語を使って予測するというN-gramモデルが古くから今でも使われてますし、データ圧縮でもこれと全く同じように履歴を使って次の文字を予測し、その予測確率を用いて符号化するPPMモデルがあります。 ここで問題になるのは、何文字前まで見れば次の文字を予測できるかということが一般のデータだと分からないということです。例えば4文字前まで見た場合より5文字前まで見たほうが次の文字が確実に予想できそうですが、4文字前までは過去のデータで何回もでているのに5文字になると途端に出現回数が少なくなってサンプル数が少なくなってしまい予測精度が低下してしまう問題があります。 そのため大抵は1,2,3..,N文字前の文
![DO++ : マルコフ情報源上で次の文字を予測する](https://cdn-ak-scissors.b.st-hatena.com/image/square/a0aa051048cb3afda5716214159b2dba29aaa425/height=288;version=1;width=512/http%3A%2F%2Fhillbig.cocolog-nifty.com%2F.shared-cocolog%2Fnifty_managed%2Fimages%2Fweb%2Fogp%2Fdefault.png)