月: 2015年1月

最近、力を入れて研究しているテーマ、それが
　Ulam距離向け誤り訂正符号
です。

簡単に言うと、
　窓表示で表示した置換に対する削除誤りに耐性を持つ置換集合を作る
ということ。

例えば、５次の置換の部分集合を { [1,2,3,4,5], [5,4,3,2,1] } の２元からなる集合とします。
そこで問題：
　数列 [ 2, 3, 4, 5 ]は、先の２元集合の元の成分の一部を削除したものです。
　二つのうち、どちらでしょうか？

答えは、[1,2,3,4,5]の方です。これの最初の成分[1]を削除したら、[2,3,4,5]になります。
ちなみに、[5,4,3,2,1]から何かを削除しても、[2,3,4,5]にはなりません。

続いて問題：
　数列 [1] は、先の２元集合のどちらかの元の一部を削除してものでしょう？

答えは、二つの元どちらも、です。
[1,2,3,4,5]の後ろの４つの成分[2,3,4,5]を削除しても、
[5,4,3,2,1]の最初の４つの成分[5,4,3,2]を削除しても、
どちらも[1]になります。

いま考えているのは、
　n次の置換の部分集合で、 n/2 個の成分を削除しても、一意に元に戻せる集合を作る
という問題。

文献調査の中で、この分野のパイオニア的な仕事である、
Levenshteinの論文
On perfect codes in deletion and insertion metric,
Discrete Mathmatics and Applications, vol.2, no.3, pp.241-258, 1992.
を読みました。
これが、凄い面白い。
感動した。

この理論を土台に拡張したい。
でも、難しい。

そんな毎日を過ごしています。

さて、写真のコーナー。

なぜか、１つのロープだけに群がる鳥たち。
なぜ？？

Tweet