Nick Johnson のブログDamn Cool Algorithms: Fountain Codesに触発されて、 Luby Transform (LT) コードの実装に挑戦することにしました。GitHubにプッシュしました。Python 3 で書かれています。
「hello」だけで構成される非常に短いファイルを使用して開発し、ランダムに生成された 1 MB のファイルでテストしました。ソフトウェアは、元のファイルの長さ、ブロックサイズ、およびエンコーダーとデコーダーの間で共有されるドロップレットのみを使用して、ファイルを効果的にエンコードおよびデコードしているようです。
問題は、これが実際に LT コードの忠実な実装であることをどのように証明すればよいかということです。デコード アルゴリズムが効率的であることを証明するにはどうすればよいですか?
使用されたドロップレットは、Python のカウントされた参照システムによって削除されることが私の意図でした。これが実際に発生していることを確認するにはどうすればよいですか?
コード自体に関するフィードバックも歓迎しますが、(回答ではなく) コメントとして、または GitHub の問題として適切な場合があります。