情報圧縮の記事となります。今回はいまいちな知名度を誇る反辞書を利用した手法についてべらべらと供述する予定です。
反辞書(antidictionary)
従来の一般的な辞書とは異なり、入力系列に出現しない系列(極小禁止語)を登録する辞書です。極小禁止語とは、それ自身は入力系列に出現せず、極小禁止語の真の部分系列は全て入力系列に出現する系列です。
すなわち、入力系列に出現しない系列の中で極小性をもつ。反辞書は全ての部分系列を登録する辞書よりも、登録する系列が少ないという性質をもつ。
また、反辞書を構成するData構造として、極小禁止語を受理するAutomatonや、接尾辞木を拡張して極小禁止語のnodeを追加するなど効率的な検索方法が提案されています。
反辞書は、Crochemore らが2000年に提案した無歪みData圧縮法に初めて用いられ、符号化で使用される確率modelの作成において有効性が示されました。
との事ですが詳細はこことかそこ辺りを熟読しまくって頂くとわかりやすい。
実装編
接尾辞Trieという構造を使います。お気軽お手軽足軽なHTML+JavaScriptで簡単動作検証。実用性皆無。
入力は0と1のみ受け付けております。いわゆるbinary列。なんという不親切設計…。
<!DOCTYPE html><html><head>
<meta charset=utf8><meta name=viewport content="width=device-width,initial-scale=1.0">
<title>Suffix Trie Compression</title>
<style>
*{font-family:MS Gothic,monospace}
body{max-width:800px;margin:0 auto;padding:20px;background:linear-gradient(135deg,#1e3c72,#2a5298);color:#fff;min-height:100vh}
.container{background:rgba(255,255,255,.1);backdrop-filter:blur(10px);border-radius:15px;padding:30px;box-shadow:0 8px 32px rgba(0,0,0,.3)}
h1{text-align:center;margin-bottom:30px;color:#fff;text-shadow:2px 2px 4px rgba(0,0,0,.5)}
.input-group{margin-bottom:20px}
label{display:block;margin-bottom:8px;font-weight:700;color:#e0e0e0}
input{width:100%;padding:12px;border:none;border-radius:8px;background:rgba(255,255,255,.9);color:#333;font-size:14px;box-sizing:border-box}
button{background:linear-gradient(45deg,#4caf50,#45a049);color:#fff;padding:12px 24px;border:none;border-radius:8px;cursor:pointer;font-size:16px;font-weight:700;transition:.3s;box-shadow:0 4px 15px rgba(76,175,80,.3)}
button:hover{transform:translateY(-2px);box-shadow:0 6px 20px rgba(76,175,80,.4)}
.output{background:rgba(0,0,0,.3);padding:20px;border-radius:10px;margin-top:20px;border-left:4px solid #4caf50}
.result-item{margin:10px 0;padding:8px;background:rgba(255,255,255,.1);border-radius:5px}
.highlight{color:#4caf50;font-weight:700}
.error{color:#f44;background:rgba(255,68,68,.1);border-left-color:#f44}
</style></head><body>
<div class=container>
<h1>AntiDictionary + Suffix Trie Compression Algorithm</h1>
<div class="input-group">
<label for=binaryInput>binary文字列を入力してください(0と1のみ):</label>
<input type=text id=binaryInput placeholder="例: 1101001010" value=1101001010>
</div>
<button onclick="compressString()">圧縮実行</button>
<div id=output></div>
</div><script>
class SuffixTrie{
constructor(t){
t += '$';
for(let i=0,l=t.length,r=this.root={};i<l;)
for(let j=i++,cur=r,c;j<l;)
cur=cur[c=t[j++]]||(cur[c]={})
}
followPath(s){
let cur = this.root;
for(let i = 0,c,l=s.length; i < l;cur = cur[c]){
c = s[i++];
if(!(c in cur))return null
}
return cur;
}
hasSubstring(s){
return this.followPath(s) !== null;
}
hasSuffix(s){
const node = this.followPath(s);
return node !== null && '$' in node;
}
isAf(s){
const node = this.followPath(s);
return node !== null && '%' in node;
}
convertAD(){
for(let q=[this.root],c;q.length;q.shift())
c=q[0],
c[0]?q.push(c[0]):c[0]={'%':{}},
c[1]?q.push(c[1]):c[1]={'%':{}}
}
}
function encode(ad, myT){
let encoded = "", curPrefix = "";
encoded += myT[0];
curPrefix += myT[0];
for(let i = 0, l=myT.length;++i<l;){
const char = myT[i];
if(ad.isAf(curPrefix + '0')){
curPrefix += char;
continue
}
if(ad.isAf(curPrefix + '1')){
curPrefix += char;
continue
}
curPrefix += char;
encoded += char;
}
return encoded;
}
function decode(ad, lenInput, encoded){
let decoded = encoded[0], curPrefix = encoded[0];
encoded = encoded.substring(1);
for(let i = 0;++i<lenInput;){
if(ad.isAf(curPrefix + '0')){
decoded += '1';
curPrefix += '1';
continue
}
if(ad.isAf(curPrefix + '1')){
decoded += '0';
curPrefix += '0';
continue
}
if(encoded.length > 0){
decoded += encoded[0];
curPrefix += encoded[0];
encoded = encoded.substring(1)
}
}
return decoded
}
function compressString(){
const binaryInput = document.getElementById('binaryInput').value.trim();
const outputDiv = document.getElementById('output');
// validation
if(!binaryInput)return outputDiv.innerHTML = '<div class="output error"><strong>error:</strong> 入力文字列が空です</div>';
if(!/^[01]+$/.test(binaryInput))return outputDiv.innerHTML = '<div class="output error"><strong>error:</strong> 0と1のみを含む文字列を入力してください</div>';
try{
console.log(`入力文字数: ${binaryInput.length}`);
console.log(`user入力(binary): ${binaryInput}`);
const myTrie = new SuffixTrie(binaryInput);
myTrie.convertAD();
const inputLength = binaryInput.length;
const encoded = encode(myTrie, binaryInput);
const compressionRatio = inputLength / encoded.length;
const spaceSavings = (1 - (encoded.length / inputLength)) * 100;
console.log(`encode済み: ${encoded}`);
console.log(`圧縮率: ${compressionRatio}`);
console.log(`容量削減: ${spaceSavings}%`);
const decoded = decode(myTrie, inputLength, encoded);
console.log(`decode済み: ${decoded}`);
console.log(`decode文字数: ${decoded.length}`);
console.log(`元の入力文字数: ${inputLength}`);
// 結果表示
outputDiv.innerHTML = `
<div class=output>
<h3>圧縮結果</h3>
<div class="result-item">
<strong>元の文字列:</strong> <span class=highlight>${binaryInput}</span>
</div>
<div class="result-item">
<strong>元の文字数:</strong> <span class=highlight>${inputLength}</span>
</div>
<div class="result-item">
<strong>圧縮後:</strong> <span class=highlight>${encoded}</span>
</div>
<div class="result-item">
<strong>圧縮後文字数:</strong> <span class=highlight>${encoded.length}</span>
</div>
<div class="result-item">
<strong>圧縮率:</strong> <span class=highlight>${compressionRatio.toFixed(2)}</span>
</div>
<div class="result-item">
<strong>容量削減:</strong> <span class=highlight>${spaceSavings.toFixed(2)}%</span>
</div>
<div class="result-item">
<strong>復元結果:</strong> <span class=highlight>${decoded}</span>
</div>
<div class="result-item">
<strong>復元成功:</strong> <span class=highlight>${binaryInput === decoded ? '? はい' : '? いいえ'}</span>
</div>
</div>`;
}catch (error){
outputDiv.innerHTML = `<div class="output error"><strong>error:</strong> ${error.message}</div>`;
console.error('Error:', error);
}
}
// Enter keyでも実行可能にする
document.getElementById('binaryInput').onkeypress=function(e){
e.key === 'Enter'&&compressString()
}
</script>
codepen召喚
See the Pen AntiDictionary by xezz (@xezz) on CodePen.