シャノン符号化により作成した正整数符号の符号語後部に, LevenshteinやEliasの符号(ω)のような長さ情報を定数回(2回以上)拡張する構造の符号で, 正整数nのlog^*_2n-α^*ω^*(n)+βlog_2ω^*(n)+O(1)ビットでの2値符号化を時間計算量O(log n)でできることを示す. ただし, 一部の符号語は符号設計時に決定しておく. ここで, log^*_2n=log_2n+log_2log_2n+log_2log_2log_2n+…である. log^*_2nは値が0以上の項のみを加える. ω^*(n)はその加える項の数である. α^*=log_2log_2e, β>1である.