文法圧縮に関連した記事となります。大雑把に言うと、部分文字列を頻度付きの木に格納し、それに関連付けた値を効率的に見つけることができるようにします。その値とは削減bits、cost、効率比の3つで、以下のような計算式で求めます。
- 削減bits = 文字列長 x 文字列頻度 x 8
- cost = 文字列長 + 文字列頻度 x 2
- 効率比 = 削減bits / cost
部分文字列を格納する符号語を2 bytesと仮定しているので、costは文字列長 + 文字列頻度 x 2となっています。抽出した文字列を効率比の降順で整列して表示します。上位にある部分文字列から優先的に圧縮していけば良いかも?
実装編
<!DOCTYPE html><html><head>
<meta charset=utf8>
<meta name=viewport content="width=device-width, initial-scale=1.0">
<title>pick up substring</title>
<style>
*{font-family:'MS Gothic',monospace}
body{padding:0;background-color:#1e1e1e;color:#d4d4d4;line-height:1.6}
h1{color:#569cd6;text-align:center;margin:0}
.input-section{background-color:#2d2d30;padding:20px;border-radius:8px;margin-bottom:20px}
textarea{width:100%;height:120px;background-color:#1e1e1e;color:#d4d4d4;border:1px solid #3c3c3c;border-radius:4px;padding:10px;resize:vertical}
button{background-color:#0e639c;color:#fff;border:none;padding:10px 20px;border-radius:4px;cursor:pointer;font-size:16px;margin-top:10px}
button:hover{background-color:#17b}
.output{background-color:#0d1117;border:1px solid #30363d;border-radius:6px;padding:16px;margin:20px 0;white-space:pre-wrap;max-height:400px;overflow-y:auto}
.section-title{color:#58a6ff;font-weight:700;margin-top:30px;margin-bottom:15px;border-bottom:2px solid #30363d;padding-bottom:8px}
input[type=text]{background-color:#1e1e1e;color:#d4d4d4;border:1px solid #3c3c3c;border-radius:4px;padding:8px;width:300px}
label{color:#d4d4d4;font-weight:700}
.results-table{background-color:#0d1117;border:1px solid #30363d;border-radius:6px;padding:16px;margin:20px 0;overflow-x:auto}
table{width:100%;border-collapse:collapse}
td,th{text-align:left;padding:8px 12px;border-bottom:1px solid #30363d}
td{white-space:pre-wrap}
th{background-color:#161b22;color:#58a6ff;font-weight:700}
tr:hover{background-color:#262c36}
td b{background:#550;color:#cc0;border:1px solid gold}
td:first-child{word-break:break-all;max-width:200px}
</style></head><body>
<h1>pick up substrings</h1>
<div class="input-section">
<label for=inputText>入力文字列:</label>
<textarea id=inputText placeholder="ここに解析したい文字列を入力してください...">This is a sample text for compression analysis. This text contains repeated patterns and words.</textarea><br>
<label>window size:
<input type=text id=windowLengths value="10,20,40,60" placeholder="例:10, 20, 40, 60"></label>
<button onclick="windowLengths.value=genWinLen(inputText.value)">自動計算</button>
<button onclick="processText()">解析開始</button>
</div>
<div class="section-title">🌳 木構造表示</div>
<div id=treeOutput class=output>解析結果がここに表示されます...</div>
<div class="section-title">📊 効率性分析結果</div>
<div class="results-table">
<table>
<thead><tr><th>pattern<th>hits<th>削減bits<th>cost<th>効率比
<tbody id=resultsBody><tr><td colspan=4>
</table>
</div>
<script>{
function genWinLen(A){
let a=0,z=A.length,b=z>>4||1,c=0,L=[];
if(b>10)b=10;
for(z-=z>>1;a<z;)L[c++]=a+=b;
return L
}
// 木を成長させる関数
function growTree(root, text, limit){
if(!text)return;
let c=text[0],node = root.find(n=>n[0]===c);
if(node){
if(node[3])return;
text.length>limit||node[1]++;
node = node[2]
}else root.push([c,1,node=[]]);
growTree(node, text.slice(1), limit);
}
// blockを配置する関数
function putBlocks(node){
if(!node.length||node[3])return;
if(node[1] === 1)return node[3] = 1;
if(node[2].length)
for(node of node[2])putBlocks(node)
}
// 木の文字列Dataを取得する関数
function getTreeText(node, value, text, save){
if(!node.length)return;
if(node[1] < value)save.push([text, value]),value = node[1];
if(node[2].length){
text+=node[0];
for(node of node[2])getTreeText(node, value, text, save)
}
}
// 木を表示する関数
function printTree(node, value, text, save){
if(!node.length)return;
if(node[1] < value)save.push(`${text} (${value})`),value = node[1];
if(node[2]&&node[2].length){
text+=node[0];
for(node of node[2])printTree(node, value, text, save)
}
}
// 主処理関数
function processText(){
// 入力を取得
let text = document.getElementById('inputText').value;
if(!text)return alert('文字列を入力してください');
let W = document.getElementById('windowLengths').value.match(/\d+/g);
if(!W)return alert('window幅の形式が正しくありません。例:10, 20, 40, 60');
// window幅を解析
for(let i=W.length;i;)W[--i]>>>=0;
// 主処理
let root = [],wn = 0,l=text.length;
for(let w of W){
// 異なるwindow幅で木を成長させる
for(let i=-1, m=l-w;i<m;)
growTree(root, text.slice(++i, i+w), wn?w-W[wn-1]:w);
// blockを配置
for(let node of root)putBlocks(node);
wn++
}
displayTree(root);// 木表示
analyzeEfficiency(root)// 効率性分析
}
// 木表示関数
function displayTree(root){
let treeOutput = [];
treeOutput.push('Proper printed version:');
for(let node of root)
printTree(node, node[1], '', treeOutput);
document.getElementById('treeOutput').textContent = treeOutput.join('\n');
}
// 効率性分析関数
function analyzeEfficiency(root){
let treeData = [];
for(let node of root)getTreeText(node, node[1], '', treeData);
// 重複を除去
treeData = new Set(treeData.map(a=>JSON.stringify(a)));
treeData = Array.from(treeData).map(a=>JSON.parse(a));
// 効率性計算と整列
for(let v of treeData){
let l=v[0].length;
v[2]=v[1]*8*l;
v[3]=v[1]*2+l;
v[4]=v[2]/v[3]
}
// 結果表示
displayResults(treeData.sort((a,b)=>b[4]-a[4]))
}
// 結果表示関数
function displayResults(sortedTreeData){
let tbody = document.getElementById('resultsBody');
if(!sortedTreeData.length)
return tbody.innerHTML = '<tr><td colspan=4>Dataが見つかりませんでした';
tbody.innerHTML = '';
for(let data of sortedTreeData){
let row = document.createElement('tr');
row.innerHTML =
`<td><b>${escapeHtml(data[0])}</b>
<td>${data[1]}
<td>${data[2]}
<td>${data[3]}
<td>${data[4].toFixed(4)}`;
tbody.appendChild(row)
}
}
// HTML escape関数
function escapeHtml(text){
const div = document.createElement('div');
div.textContent = text;
return div.innerHTML
}
}</script>
試運転
See the Pen pick up substrings by xezz (@xezz) on CodePen.
window sizeとかいう項目は木を成長させる幅とでも思っていて下さい。訳が分からん場合は入力文字列の欄を更新するごとに自動計算して下さい