LZアルゴリズムでBase62に圧縮するJavaScriptライブラリ書きました

LZSS(LZ77) 圧縮アルゴリズムで文字列を圧縮/解凍します。
圧縮された結果は Base62 (0-9A-Za-z) からなるバイナリセーフな文字列になります。
サイズ制限のある localStorage や sessionStorage, cookie など、 例えば localStorage は 5MB 使えたとしても UTF-16 の場合、実質的に 2.5MB 分になってしまします。
圧縮結果は内容にもよりますが おおよそ 60～80% 程度のサイズになります。
例外として、繰り返しのない文字列は1～2割程度サイズが増えることがあります。

追記

2014-10-24 現在、高速化にすべく見なおして圧縮率も上がりました。
繰り返しのない文字列 (例えば U+0000 - U+FFFF １文字ずつなど) も大幅なサイズ増加なく圧縮できます

var data = 'hello hello hello';
console.log(data.length); // 17

var compressed = lzbase62.compress(data);
console.log(compressed); // 'tYVccfrgxGL'
console.log(compressed.length); // 11
console.log(compressed.length < data.length); // true

var decompressed = lzbase62.decompress(compressed);
console.log(decompressed); // 'hello hello hello'
console.log(decompressed === data); // true

Download

• lzbase62 Releases

※バージョンが違うとフォーマットも違う可能性があります。できるだけ最新バージョンをご利用ください

Demo

• Demo

Repository

• polygonplanet/lzbase62 - GitHub

ランレングス法をJavaScriptの正規表現で書いてみた

ランレングス法は、BMP などに使われるデータ圧縮アルゴリズムです

連続したデータが多ければ圧縮率は上がりますが、
そうでない場合、逆にデータ量が増えることもあります

// ランレングス圧縮/解凍
var RunLength = {
  compress : function(s) {
    return s.replace(/([\s\S])\1{0,8}/g, function(a, c) {
      return c + a.length;
    });
  },
  decompress : function(s) {
    return s.replace(/([\s\S])(\d)/g, function(a, c, n) {
      return new Array(++n).join(c);
    });
  }
};

• 動作サンプル

JavaScriptだけでzipファイルの解凍 - Unzipper.js

とつぜん書いてみました。

• デモページ

デモページを開いて、デスクトップなどから zip ファイルをドロップすると
再帰的に解凍して結果のテキストを表示します。

非同期 + Pot.js イテレータ を使って実装したくて作ってみました。
zlib inflate を非同期化しています。
数GB の zip も、CPU 負荷を抑えつつ「応答のないスクリプト」警告なしに解凍できましたが
ブラウザによって、ファイルドロップの時点である程度サイズがあると無効になるようです。

レポジトリ

• polygonplanet/Unzipper.js - GitHub

その他、なにか問題等あれば
コメントやメールまたは @polygon_planet まで送っていただけるとうれしいです。

同期処理を非同期に変換-JavaScriptライブラリPot.js+PotLite.jsリリースノート

Pot.js 1.14 と PotLite.js 1.31 リリースしました。



その前に Pot.js + PotLite.js リファレンス が完成しました (ということにしたい) ので、
お時間あるときにでも覗いてみてください。

結局 /test-for-new-design/ に置いてあるのはファイル消すのも嫌だし
全部リダイレクトさせるようにしました。



Pot.js 1.14 と PotLite.js 1.31 では、Pot.deferreed() ていう関数つくりました。

deferreed は、関数の中の for, for-in, for-of, do, while 等の同期ループを
Pot.Deferred.forEach() などの非同期イテレータに置き換えて関数を再定義します。

前の記事「JavaScript whileループとPot.Deferred.forEverイテレータでCPU使用率を比較」 でも書いてますが、
Pot.js ライブラリのイテレータは CPU の負荷なく実行できます。

ループを置き換えることで、巨大な文字列を扱ったり、ループ回数が未知な処理をする際に
重さについて考えなくて済むようにと、作ってみまみた。

もともとは deferrize() という関数から派生しています。

関数内のコードをトークン単位に分解して、
単純にトークンの数が多いループブロックをメインループとして解析して、
その文に見合った Pot.Deferred イテレータを割り当ててるんですが
ぜんぜん思ったよりたいへんで まだ複雑なものは対応できてないです。
とくに三項演算子 (?:) と function のコンボとか、E4X とかまでは今後の課題。。 にしたいけど、
そこまでしてたらライブラリの方向性違うんじゃないのって思ってしかたないです。

deferreed の 1 コールで zip.deflate 圧縮とかファイル規模への md5 とか非同期化できたら楽そう。

例えば以下のような関数が

// 文字列を charCode からなる配列にして返す関数
var toCharCode = function(string) {
    var result = [];
    for (var i = 0; i < string.length; i++) {
        result.push(string.charCodeAt(i));
    }
    return result;
};

// deferreed により for 文を非同期イテレータにした関数を生成
var toCharCodeDefer = Pot.deferreed(toCharCode);

// 例えば toCharCodeDefer は内部で以下のような感じに変換される
//
//  function(string) {
//      var result = [];
//      return Pot.Deferred.repeat(string.length, function(i) {
//          result.push(string.charCodeAt(i));
//      }).then(function() {
//          return result;
//      });
//  };
//

// Pot.Deferred インスタンスが返るため then() などで繋げられる
toCharCodeDefer('abc').then(function(res) {
    Pot.debug(res); // [97, 98, 99]
});

// この変化により、巨大な文字列でも負荷を分散させ実行できる
var largeString = new Array(100000).join('abcdef');

// 'slow' などの指定が可能
toCharCodeDefer.slow(largeString).then(function(res) {
    Pot.debug(res.length); // 599994
});

あと、プラグインみたいなことしたくて Pot.Plugin ての作ったんですが
なにか違うような気がしてならないです。

プラグイン = ただのオブジェクト
になってしまった。

Pot.addPlugin() という関数で任意の関数とかオブジェクトを登録。
Pot.removePlugin() で削除。
Pot.hasPlugin() で確認、Pot.listPlugin() で列挙。

addPlugin した関数は Pot.xxx でアクセスできる。
・・・それって Pot.myFunc = function() {}; でいいじゃん! てなったので、
以下のようにしてみました。

var string = '\t abc\n \t ';

// オリジナルの Pot.trim()
debug(Pot.trim(string)); // 'abc'

// プラグイン関数の登録により Pot.trim() を上書き
Pot.addPlugin('trim', function(s) {
    return s.replace(/^ +| +$/g, ''); // スペース (U+0020) だけ削除するようにする
});

// 登録した Pot.trim()
debug(Pot.trim(string)); // '\t abc\n \t'

// プラグインの trim を削除
Pot.removePlugin('trim');

// 元に戻る
debug(Pot.trim(string)); // 'abc'

元に戻せる (むしろ消えない) ので、
一時的に挙動を変えたい時とか便利かもしれないです。
あと、Pot.globalize() したときに プラグイン関数もグローバル化します。
Pot.globalize() しなくても with (Pot) {...} でもいい気がしてきました。

プラグインの詳細は
Pot.Plugin リファレンス あたりから参照ください。

マニュアルは英語版も含めてちょっとずつ進めています。

---

以下はレポジトリとかのリンクなど。

Pot.js / PotLite.js

Pot.js は CPU に負荷をかけることなく JavaScript の実行を可能とするユーティリティライブラリです。
PotLite.js は Pot.js の非同期な部分だけを抽出したライトバージョンです。

ダウンロード

• Pot.js / PotLite.js 最新

マニュアル

• Pot.js + PotLite.js - Document and Reference - JavaScript Async Utility Library

その他の情報についてはマニュアル/マニュアルからのリンク から参照ください。

レポジトリ

• polygonplanet/Pot.js - GitHub

その他、なにか問題・バグ・感想・指摘などあれば、
コメントやメールまたは @polygon_planet まで送っていただけるとうれしいです。

「Audio」と「Bookmark」をポスト一覧に追加するTomblooパッチ

Firefox アドオン Tombloo のパッチです。

パッチといっても今回のはすごく…大きいです…。機能が多すぎて列挙しきれませんので
簡単に言うと、Photo とか Link, Quote の他に 「Bookmark」 と 「Audio」 を追加するパッチです。
Bookmark は、省略しがちなタグやコメントを入力しやすくしたもので、Audio はオマケです。

概要

もともとは、Google ブックマークアドオンの GMarks を使うのやめて
Tombloo で全部統一しようと思ったのがきっかけだったと思いますが、
細かい修正パッチを重ねてくうちに折角だからと他のサービスも手を出して
はてブ、GoogleBookmarks、Delicious、Yahoo!Bookmark、Firefoxのブックマークなど、
主なソーシャルブックマークサービスで殆ど同じに使えるように
おすすめタグの出ないものはキーワード解析し表示するようにし、
タグ名やコメントの最大文字数によるエラーが発生しないよう機能を追加したり
結局のところ細かいところまで機能実装してるパッチの集合体みたいになってます。
Audio は、Constellation さんが作ってる Taberareloo がすでに実装してるので、
それを元にさせていただいて Tombloo でもリブログなど可能になっています。

上の画像の設定ダイアログのように、「Audio」 と 「Bookmark」 が追加されます。

機能

• Posters に 「Bookmark」 と 「Audio」 を追加実装
• 設定ダイアログ内にチェック可能な 「Bookmark」 と 「Audio」 を追加
• Audio のリブログと mp3, wav, ogg, mid, midi リンクからのポストを実装
• Audio のローカル保存を実装
• ブックマーク用の POST ダイアログを追加実装
• はてなブックマーク、GoogleBookmarks など主なサービス対応
• 主なブックマークエラーを修正および改善
• POST ダイアログのコンテキストメニューを拡張
• Quote したテキストの 「HTML」 と 「PlainText」 を切り替え表示できる項目追加
• POST ダイアログが表示されたとき画像が小さいままになる状態を修正
• POST ダイアログが半分消えてる状態になって現れた場合のフィックス
• タグ補完時に左右キー(←→)で補完窓を閉じられるようイベントを追加
• POST 時にタグ名をユニークにして重複防止
• タグ名の大文字小文字をユーザー側優先で扱うよう改善(おすすめタグなど)
• ブックマーク時に文字数オーバーでエラーになるのを自動で調整カット
• ブックマーク済みかどうかを明確にわかるよう改善
• タグ付け補助用のキーワード抽出などをメニューに追加
• パッチのバージョン確認と自動アップデート機能を実装
• メニューからクリックするだけでパッチのアンインストールが可能
• FirefoxBookmark などおすすめタグが無いサービスでもキーワードを表示する機能
• タグ名補完で読みが想定外なものを本来の読みに一部修正

ほかにも機能や修正などありますが、内部的なことも含むので省きます。

POST フォームはこんな感じです。
タグ入力欄の下に表示される おすすめタグは、
Firefoxブックマークや GoogleBookmarks でも利用できます。

コンテキストメニューを拡張しています。
上の画像では HTML タグ補助ですが、他にもたくさんあります。
あまりに多いのでここでは説明を省きます。たぶん使ってみるとわかります。

トップメニューの 2 つだけ説明すると、
「キーワード抽出」 は、そのページ内の文章からキーワードを抽出し、
テキスト入力欄に結果をだします。

どのメニューも、その時入力されているテキストが対象の場合
テキスト全体を置換する動きをします。
つまりその時のテキストは失われますのでご注意ください。
でも 「元に戻す」 が有効であれば戻ります。

「マルコフ連鎖で要約」 は、入力欄のテキストもしくは 「キーワード抽出」 と同じく、
そのページ内から文章を取得し、マルコフ連鎖というアルゴリズムで文章を要約し
テキスト入力欄に結果を出します。
あまり賢くはないです。

この 2 つのメニューアイテムは、
タグの他にコメントも検索対象としてるブックマークサービスがあるため、
その目的を楽に済ますために付けました。
でも、過度な期待はしないでください。

設定ダイアログのポスト関連です。

「ショートカット - Bookmarkクイックポスト」

これはインストール時に 「CTRL + D」 に設定されます。 通常のブラウザのブックマークの代わりに Tombloo Bookmark のダイアログが出ます。 任意に変更してください (リセットする場合 エスケープキー 「Esc」 です)。

「自動挿入するタグ」

ここに入力したタグは、最優先で常に送信するタグに付きます。

「非公開でブックマークする」

そのままですが、プライベートモードがサポートされてるサービス限定です。 Delicious や YahooBookmarks は利用できます。 チェックをつけておくと、それらのサービスでは常に非公開になります。

あと、いま画像見て気付きましたが…、
「Faves」 と 「LivedoorClip」 は実装してません (Tombloo 既存の機能のみ使える)。
需要あるようでしたら、コメントください。

次のタブの設定ダイアログです。

「メディア(Photo等)をフォルダ分けして保存」

これにチェックを入れると、ローカル (Local) に保存する際、 Photo (画像) を、 ホスト名別でフォルダを作り保存するようになります。 例えばこのブログの画像をローカルにポストした場合、 「photo」 フォルダの中に 「polygon-planet-log.blogspot.com」 というフォルダが作られ その中に画像が保存されます。 この機能によって、一つのフォルダに大量に保存され開けなくなったなど解消されますが、 デメリットとして、同じ画像が複数のホストにあった場合、重複画像が増えます。 なお、「audio」 も、このチェックで作用します。

Quote で選択したテキスト入力欄でコンテキストメニューを開くと、
「テキストと HTML を切り替え」 というメニューが現れます。
この機能は、プレーンテキストと HTML を切り替えて表示します。

アイコンが カラー の時は 「HTML 表示中」 の状態。

アイコンが グレー の時は 「プレーンテキスト表示中」 の状態です。

最終的に送信されるのは、1 文字でも編集した場合は 表示中のテキストになり、
まったく編集してない場合は、HTML が送信されます。
たとえ HTML 表示中にして、入力欄を空にしても
結局は Tombloo 内部で元の HTML を保持しているので
HTML 表示にして編集した後、
送信するときには 未編集のプレーンテキストに切り替えてた場合、
HTML が送信されることになります。

分かり難い…。

このパッチの機能 「HTML ⇔ プレーンテキスト 切り替え」 は、
2 つのテキストボックスがあってそれを交互に表示切り替えしてるわけではなく
単にテキスト入力欄の文字列を 2 つのデータで入れ替えてるだけです。

Tombloo の Quote テキストは、
テキストを選択して クイックポストフォーム を開いたときに
HTML と プレーンテキスト の両方が保持されます。
そして、送信時 (POST ボタン押下時) に入力欄のテキストが
保持していたプレーンテキストと違えば入力欄のテキストを使い、
同じだった場合は保持していたデータのうち、HTML が優先して使われます。

たんにプレーンテキストで送信したい場合は、
プレーンテキスト表示で改行やスペースなど 1 文字でも変えればいいわけです。

今まで通りの使い方をしたい場合は、そのままポストでいいと思います。

注意というかプレーンテキストの改行は自動で
タグなどは付かないです。

このパッチは自動でアンインストールとアップデートができます。

なぜかというと、/tombloo/chrome/content フォルダの中のスクリプトを置換しているからです。
そのため、インストール時にバックアップを作り、アンインストール時に元に戻しています。
その影響で、既にユーザーの手でソースコードが編集されてる場合や
ファイル名が変わっていたりパスが違ったりするとインストール/アンインストール共に失敗します。

置換/バックアップするファイル:

• tombloo/chrome/content/quickPostForm.xul
• tombloo/chrome/content/prefs.xul
• tombloo/chrome/content/completion.xml
• tombloo/chrome/locale/ja-JP/tombloo.dtd
• tombloo/chrome/locale/en-US/tombloo.dtd

インストール/アンインストール/アップデートのチェックはしましたが、
編集済みの環境の場合、インストールする前にバックアップをとってください。
編集済みでなくても、できるだけバックアップしたほうがいいです。

とくに Mac 環境で テスト出来ていないので、Mac で動いた場合は報告いただけると嬉しいです。
他にもバグや要望があればコメントまたはメールか @polygon_planet で伝えてくれるとうれしいです。

そしてめずらしく長々(?)と書きましたが、そういう理由で
あえて下のほうにインストール/ダウンロードリンクを置きました。
このパッチは理解なしでインストールして途中で失敗すると戻せなくなる可能性があるのです。
ここまでやるならフォークしたほうがよかったんじゃ…とか思ったけどそれにはまだまだ…。
他にも書くことあった気がするけど忘れました…。

追記
思い出しました。
「HTML ⇔ PlainText 切り替え」 は、HTML のテキストを可視化することで
巧妙な方法で スクリプトが埋め込まれてる場合に確認 できるようにと付けた理由もあります。
Tombloo は、ある程度の サニタイジングを行いますが 100% ではないのです。
とは言っても滅多にないと思います。
Quote したら確認程度に一度、切り替えてみるといいかもしれません。

パッチ (Download):

• tombloo.poster.bookmark.pot.assort.js

インストール:

上のパッチリンクを
右クリック→「Tombloo」→「Tomblooパッチのインストール」でインストール。


※直接右クリックからインストールできない場合:

できない場合は

「Tomblooパッチのインストールに失敗しなくなるパッチ」 のパッチ/記事をインストールもしくは参照ください。

続き

アップデートされた機能に関する記事です。↓
「 「Audio」と「Bookmark」を追加するTomblooパッチのアップデートについて 」

レポジトリ

• polygonplanet/tombloo - GitHub