文字列間のレーベンシュタイン距離を求める

レーベンシュタイン距離というのを知った。

Wikipedia のレーベンシュタイン距離の項によると:

レーベンシュタイン距離(レーベンシュタインきょり)は、二つの文字列がどの程度異なっているかを示す距離(距離空間を参照)である編集距離(へんしゅうきょり)の一種類である。具体的には、文字の挿入や削除、置換によって、一つの文字列を別の文字列に変形するのに必要な手順の最小回数として与えられる。名称は、1965年にこれを考案したロシアの学者ウラジミール・レーベンシュタインにちなむ。

だそう。上記ページに擬似コードによる実装例が載ってるのと、次のページの Python での実装例が参考になった。なので JavaScript でやってみた。

 cf. 編集距離 (Levenshtein Distance) – naoyaのはてなダイアリー

実行例:

takatoh@nightschool $ ./ld.js apple play
4
takatoh@nightschool $ ./ld.js perl pearl
1

文字列を指定した文字数ごとに分割する

今日は Windows マシンから更新。

 cf. ruby 文字列を指定数で分割する – それマグで!

Haskell でやってみた。

^o^ > runhaskell stringSlices.hs
["abc","def","ghi","jkl","mno","pqr","stu","vwx","yz"]

Scheme だとこう。

^o^ > gosh string-slices.scm
(abc def ghi jkl mno pqr stu vwx yz)

最後に JavaScript。

^o^ > node stringSlices.js
[ 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqr', 'stu', 'vwx', 'yz' ]

これ、もうちょっとスマートにいかないかな。

[追記]

JavaScript 版、Haskell 版や Scheme 版と同じように考えてみた。少しはスマートになったかな。そうでもないか?

^o^ > node stringSlices2.js
[ 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqr', 'stu', 'vwx', 'yz' ]

100から1まで表示するコードすら書けないプログラマ

 cf. 100から1まで表示するコードすら書けないプログラマ – 新・日々録 by TRASH BOX@Eel

詳しくはリンク先を読んでもらうとして、100から1まで表示するだけのプログラムを10分たっても書けないプログラマが14%もいたという調査結果があるんだそうだ。話の雰囲気からして職業プログラマの話だろうに、FizzBuzz の話もそうだけど、こんな簡単なプログラムも書けなくて普段どうやって仕事してるんだろう?

それはともかくとして、リンク先にはいくつかの言語で書いたコードがあるけど、JavaScript がないので書いてみた。そしたら、一発じゃできなかったよ…orz。というのが今日のオチ。
以下、恥を晒しておく。

最初に書いたのがこれ。

実行してみると:

takatoh@nightschool $ node countdown.js

/home/takatoh/w/nodejs/countdown.js:1
(function (exports, require, module, __filename, __dirname) { for var i = 100,
                                                                  ^^^
SyntaxError: Unexpected token var
    at Module._compile (module.js:439:25)
    at Object.Module._extensions..js (module.js:474:10)
    at Module.load (module.js:356:32)
    at Function.Module._load (module.js:312:12)
    at Function.Module.runMain (module.js:497:10)
    at startup (node.js:119:16)
    at node.js:902:3

ああ、for のあとには括弧がいるんだっけ。

今度はいいだろう。

takatoh@nightschool $ node countdown2.js

/home/takatoh/w/nodejs/countdown2.js:1
orts, require, module, __filename, __dirname) { for (var i = 100, i > 0, i-- )
                                                                    ^
SyntaxError: Unexpected token >
    at Module._compile (module.js:439:25)
    at Object.Module._extensions..js (module.js:474:10)
    at Module.load (module.js:356:32)
    at Function.Module._load (module.js:312:12)
    at Function.Module.runMain (module.js:497:10)
    at startup (node.js:119:16)
    at node.js:902:3

おおい、どういうこった。
眺めてもわからないので Google 先生に聞くことに。そしたら、for の初期値とか終了条件とかはカンマじゃなくてセミコロンで区切るんだった。ああ、まだ身についてないな。というか、普段書いてる Ruby やら Python じゃこういう for ループ書かないからなあ(言い訳)。
というわけで、最終的にはこれで正解。

Node.js:コマンドラインオプションを処理する

js-opts というモジュールが使える。
npm でインストール。

^o^ > npm install opts
opts@1.2.2 node_modules\opts

js-opts というモジュール名だけど、インストールするのは opts。

昨日のファイル一覧を表示するスクリプトを拡張してみた。

オプションをオブジェクトの配列として定義しておいて、opts.parse の引数に渡してやると、オプション解析をしてくれる。true はなんだろう?

オプションの引数は opts.get(オプション名) で取得できる。それから、解析の結果残った引数は opts.args() で配列として取得できる。

実行結果:

^o^ > node listfiles2.js --version
v0.1.0

^o^ > node listfiles2.js --help
Usage: node C:\Users\takatoh\Documents\w\nodejs\listfiles2.js [options]
Show this help message
    --help
Specify ext
    -e, --ext 
Show version and exit
    -v, --version


^o^ > node listfiles2.js .
config.json
filesize.js
get_file.js
get_file2.js
hello.js
hello.txt
httphead.js
listfiles.js
listfiles2.js
read_config.js
server.js
test_argv.js
test_url.js

^o^ > node listfiles2.js --ext js .
filesize.js
get_file.js
get_file2.js
hello.js
httphead.js
listfiles.js
listfiles2.js
read_config.js
server.js
test_argv.js
test_url.js

–help オプションは定義しなくても、自動で作ってくれるみたい。

js-opts のサイト:

 cf. https://bitbucket.org/mazzarelli/js-opts/wiki/Home

[追記]

js-opts のソースを確認したところ、opts.parse の第2引数に true を指定すると、–help オプションを追加してくれるみたい。

Node.js:ファイルの一覧を取得する

指定したディレクトリ中のファイル一覧を取得する。
fs モジュールの readdir を使う。

^o^ > node listfiles.js .
config.json
filesize.js
get_file.js
get_file2.js
hello.js
hello.txt
httphead.js
listfiles.js
read_config.js
server.js
test_argv.js
test_url.js

Node.js:async.forEachSeries

昨日のプログラム、うまくいったので書く。

結果から書くと、アクションの中で callback を呼び出させばいいようだ。プログラムはこんなふうになった。

アクションの最後、特に getNewItem ではネストの一番深いところで callback を呼び出している。これが次のアクションを呼び出すことになっているわけだ。
実行結果。

^o^ > node replicate.js
New item: Penguins.jpg
New: Penguins.jpg...done.
New item: data/Desert.jpg
New: data/Desert.jpg...done.
Delete item: Penguins.jpg
Delete: Penguins.jpg...done.

ちゃんと指示通りの順番で実行されている。

^o^ > tree /F storage
フォルダー パスの一覧:  ボリューム OS
ボリューム シリアル番号は FE2A-F7C6 です
C:\USERS\TAKATOH\DOCUMENTS\W\REPLICATE\STORAGE
└─data
        Desert.jpg


Penguins.jpg は削除されて残っていないのがわかる。

Node.js:async.forEachSeriesって配列の順番どおりに処理してくれるんじゃないの?

本当はうまくいってから書くつもりだったけど、どうにもうまくいかないので書くだけ書いておく。

簡単な説明

サーバからの指示でファイルをダウンロードしたり削除したりするプログラムを Node.js で書いている。けど、指示通りの順番で処理してくれないので困ってしまった。async.forEachSeries を試してみたけどダメだった(←今ここ)。

より細かい説明

サーバは http://localhost:8888/ で動いていて、/recent.json にアクセスすると指示を受け取ることができる。指示は JSON 形式で、次のようなもの。

action がするべき処理を示していて、new は新しくファイルをダウンロード、delete はすでにダウンロードしたファイルを削除する。上の例では、

  1. Penguins.jpg をダウンロードして保存
  2. data/Desert.jpg をダウンロードして保存
  3. Penguins.jpg を削除

となって、結果として data/Desert.jpg だけが保存されるはず。

書いてみたプログラム replicate.js を載せるよ。

たいして難しいことはしてない。変数 action にアクションを登録(9~12行目)しておいた上で、サーバから JSON で指示を受け取り(15行目)、パースして配列に直し(22行目)、配列の順番どおりに処理している(23~25行目)。ついでに各処理のはじめと終わりにコンソールに出力している。

さて、これを実行してみると、期待通りには動いてくれない。

^o^ > node replicate.js
New item: Penguins.jpg
New item: data/Desert.jpg
Delete item: Penguins.jpg
Delete: Penguins.jpg...done.
New: Penguins.jpg...done.
New: data/Desert.jpg...done.

処理の開始は配列の順番どおり(最初の3行)だけど、Delete が先に終わってしまって、New があとになっている。結果として、削除するはずの Penguins.jpg が残っている。

^o^ > tree /F storage
フォルダー パスの一覧:  ボリューム OS
ボリューム シリアル番号は FE2A-F7C6 です
C:\USERS\TAKATOH\DOCUMENTS\W\REPLICATE\STORAGE
│  Penguins.jpg
│
└─data
        Desert.jpg


原因はアクションの処理が非同期なせいだ。Array.forEach 自体は非同期じゃないらしいけど(だから指示の順番どおりにアクションが始まっている)、アクション自体が非同期なので、ひとつのアクションが終わらないうちに次のアクションが始まり、終わりの順番が入れ替わってしまっているんだ。
これは困った。ちゃんと指示通りに順番に処理してくれないと、上のように Penguins.jpg のダウンロードと削除が指示通りにならない。さて、どうしよう。

async.forEachSeriesを試す

いろいろググってみた結果、async というライブラリでフロー制御ができるらしい、というのがわかった。というわけで、async.forEachSeries を試してみた。
書き換えたのがこのコード。

書き換えたのは2行だけ。5行目で async を読み込み、24行目では items.forEach(function… の代わりに、async.forEachSeries(items, function… としている。これで、うまく動いてくれるだろうか。

^o^ > node replicate.js
New item: Penguins.jpg
New: Penguins.jpg...done.

ダメだーーー!
なんだかわからないけど、最初のアクションしか実行してくれない。ぜんぜん each じゃないじゃないか。どういうことだろう?

Node.jsでMD5を計算する

組み込みの crypto モジュールを使う。

takatoh@nightschool $ nodejs md5.js sample.zip
ae5a874a75de5b5597091d04b55b0b42  sample.zip

Node.jsでファイルを2行ずつ処理する

昨日、1行ずつ処理する方法はわかったけど、複数行、例えば2行ずつ処理したいこともある。ググってみたら Qiita で見つけた。

 cf. ストリームを行ごとに処理~readline編~ – Qiita

真似して書いてみた。

takatoh@nightschool $ cat input.txt
3
1 2 3
4
2 4 8 16
4
2 3 5 7
takatoh@nightschool $ nodejs readline_unit.js input.txt
3:1 2 3
4:2 4 8 16
4:2 3 5 7

上の実行例では2行ずつだけど、forEach の第1引数でほかの値を指定すれば任意行ずつ処理ができる。
ただ、指定した行(とその端数)ずつしか処理できないんだよな。何行ずつ処理するかを動的には決められない。Ruby の gets みたいなのがあればいいのに。

Node.jsでファイルを1行ずつ処理する

Web で見つけてきた JavaScript の動作検証をしようと、ファイルからデータ(1行に1データ)を読み込んで処理する方法を探したら見つかったのでメモ。

 cf. Node.jsでテキストを1行ずつ処理する – console.lealog();

takatoh@nightschool $ cat input.txt
1
2
3
4
5
6
7
8
9
10
takatoh@nightschool $ nodejs readline.js
10
20
30
40
50
60
70
80
90
100