Home > プログラム Archive

プログラム Archive

命名辞典

最近何をしていたのか。
Androidアプリの開発を手伝っていました。

命名辞典

名字を入力すると画数から姓名判断して、最も幸運な名前を教えてくれます。
こいつぁ便利だぜ!

バグ・要望などありましたら是非ともよろしくお願いいたします。

今後いろいろ作っていきたい、というかネット航海時代をアプリ化したい。
いやまじで。

以上

Save Pages

mycodestockというWebサービスがある。
https://mycodestock.com/
これはプログラムなどのソースのスクラップを簡単に保存できる便利なサービスだ。
私はその簡潔さから便利に大変活用させてもらっている。長らく使っている間に、かなりのソースやTipsがたまってきた。
しかしながら、世間的にはそんなに流行っていないように見える。これは非常に恐ろしいことだ。
なぜならば、いつサービスが終了するかわからないからだ。どうみても個人が運営している。
急にサービス終了するととっても困る。

ということで、とりあえずダンプしたい。ローカルに保存しておきたい。
そこでいろいろ魚拓系のサービスやらChromeの拡張機能やら探したが、うまく保存できるものがなかった。
mycodestockはログインして使うものなので、Webサービスによる魚拓は難しい。
またAjaxで動的にコンテンツが読み込まれているので、「名前を付けて保存」をしても必要なコンテンツは保存されない。
Chromeの拡張機能でスクリーンショットを撮るやつは画像で保存するやつばっかりで、それじゃコピペできないじゃんという。

仕方がないから自分で作ることにした。
Save Pages
HTMLをそのまま保存して、HTMLからページを復元する、コピペ可能なスクリーンショット。
ajaxで動的に作成されたエレメントもHTML化して保存するので安心すべし。(何しろそのために作ったのだ)
今のところ画像とかスクリプトには対応してない。要望あれば。

追記:もっといいのがあった。https://chrome.google.com/webstore/detail/gokffdfnlmampchciemmflgbckijpmlb
もっと早く知っていれば・・・!まあ、たのしかったからいいか。

以上

DoubleKeyboard更新

レイアウト変更をON・OFFするトグルキーの追加と、
レイアウト設定用のツールを同封しました。
http://red-treasure.com/main/ttbase.htm#doublekeyboard

上下左右とHOMEとENDとBSとDELをホームポジションから使えるようにしておくと
結構便利。

以上

ネット航海時代 リニューアル

ネット航海時代をリニューアルしました!

とりあえずver3βとしています。
まだまだ至らない点が多いですが、ご指摘等頂けたらありがたく思います。

Perlから無駄にPHPに移植し、全面的に作り直しました。
これから機能を増やしていく予定です。

目下の対応案件は携帯です。
twitterのoauth認証がdocomoだと文字化けしまくりでだるい感じです。でも認証はできます。

以上

chromeのエクステンション作った

なぜかchromeにはGoogleツールバーがなさそうなので、なんちゃってを作った。
SearchBarFindInPage

MigemoFindInPageをパクリまくって。
ソースをパブリックドメインで公開されていて、非常にありがたい話です。
私のソースもそのうち公開しますが、そこら中から寄せ集めただけで整理すらできていないので後日。
とっても無駄だらけのソースと思います。ま、インストールすればみれちゃうだろうけど。

動作としては、普通にアドレスバーからgoogle検索後、任意のページでマウスを上の方に持って行くとツールバーが現れます。
ボタンをクリックするとページ内検索がMigemoFindInPageのインターフェースを使ってできるという。
なんというパクリ方。

以上

KeyPointerEXを更新

KeyPointerEXを改良した。
設定を他のPCにもコピーできるように、iniファイルに保存できるようにした。
あと、マウスポインタをアクティブウインドウの真ん中と上部に移動できるショートカットを追加した。
Alt+Tabでアクティブウインドウを切り替えてもマウスポインタがついてこないからちょっと不便だったんだよな。

以上

TTBaseのプラグイン作ってみた9

SendKeyとかでがんばれば、xkeymacsとかでがんばれば、できる気がするなんちゃってキーボードレイアウト切り替え器。
ファンクションキーとテンキーをホームポジションから使うためだけに作った。
仮想キーコードを適当に割り当てればいろいろできるような気がしないでもない。

DoubleKeyboard

以上

TTBaseのプラグイン作ってみた8

3回矢印キーを連打したら自動でそのキーを送信して自動スクロールさせる奴。
何か書いているときはうざいことこの上ない。
でも私は使うのだ。ブラウジングに。
ContinueKey

以上

ttbaseのtaskext更新

taskextを更新して、メニューに出す項目をiniファイルで設定できるようにした。
自分でもちょっと危険だと思ってたから・・・。

以上

レーベンシュタイン距離の挿入コストと削除コスト

レーベンシュタイン距離っていうのは一つの文字列と文字列の距離の求め方です。
ざっくり言うと、Aという文字列とBという文字列の距離を求める場合、Aの各文字を削除したり置換したり、あるいはBにある文字をAに挿入したりしてBと同じ文字列を作り、そのときの手数を距離とします。
例えばA:”abbc”とB:”acbbd”の距離を求めると以下のようになります。

aとbの間にcを挿入→acbbc
最後のcをdに置換→acbbd

ということで距離は2です。編集の方法はいくつもありますが、最小の手数のものを距離と定義します。
例えば

aとbの間にcを挿入→acbbc
後ろのbとcの間にdを挿入→acbbdc
最後のcを削除→acbbd

だと手数が3なのでNGです。プログラムでこの最小手数を求めるにはDP法(動的計画法)を用います。
Wikipediaの解説
でも上記の擬似コードはコメントが間違っていると思います。
レーベンシュタイン距離はあくまで「Aを編集してBにするときの最小コスト」なので、編集はすべてAに対して行わなければなりません(たぶん)。なのでBの文字列を削除したりしてはイカンのです。
d[ i1, i2 ]は文字列Aのi1番目までの文字列と文字列Bのi2番目までの文字列の距離です。
A:a(1)a(2)…a(i1)
B:b(1)b(2)…b(i2)
DP法により、この距離をd[ i1 – 1, i2]、d[ i1, i2 – 1]、d[ i1 – 1, i2 – 1]を使って求めるわけですが、次のように考えるべきです。

・Aからの削除によりBに近づく場合:
Aから末尾の文字a(i1)を削除すれば「a(1)~a(i1 – 1)の文字列」と「b(1)~b(i2 – 1)の文字列」との距離に帰着されるので、d[ i1, i2 ]はd[ i – 1, i2]の距離に末尾文字a(i1)を削除するコストを足したものと等しい。
・Aへの挿入によりBに近づく場合:
a(1)~a(i1)の末尾にb(i2)を挿入すれば、
  “「a(1)~a(i1)b(i2)の文字列(A側の末尾にb(i2)を加えた)」と「b(1)~b(i2 – 1)の文字列」の距離”
  “「a(1)~a(i1)b(i2)の文字列」と「b(1)~b(i2)の文字列」の距離”
は等しくなるのでd[ i1, i2 ]はd[ i1, i2 – 1 ]の距離にb(i2)を挿入するコストを足したものに等しい。
・Aの文字を置換することでBに近づく場合:
a(i1)をb(i2)に置換すればよいので、d[ i1, i2 ]はd[ i1 – 1, i2 – 1]にa(i1)を置換するコストを足したものに等しい。

というわけで、PHPで書くと以下のようになります。


/**
 * レーベンシュタイン距離を求める。
 * @param $a A文字列
 * @param $b B文字列
 * @param $i_c 挿入コスト
 * @param $r_c 置換コスト
 * @param $d_c 削除コスト
 * @return 距離
 */
function leven($a, $b, $i_c=1, $r_c=1, $d_c=1)
{
   $len_a = strlen($a);
   $len_b = strlen($b);
   $matrix = array();
   for ($jj = 0; $jj <= $len_b; $jj++) {
      $matrix[0][$jj] = $jj*$i_c;   // 全挿入
   }
   for ($ii = 0; $ii <= $len_a; $ii++) {
      $matrix[$ii][0] = $ii*$d_c;   // 全削除
   }

   for ($i = 1; $i <= $len_a; $i++) for ($j = 1; $j <= $len_b; $j++) {
      $del = $matrix[$i-1][$j] + $d_c;   // 削除
      $ins = $matrix[$i][$j-1] + $i_c;   // 挿入
      $rep = $a[$i-1] == $b[$j-1] ? $matrix[$i-1][$j-1] : $matrix[$i-1][$j-1] + $r_c;   // 置換
      $matrix[$i][$j] = min($ins, $del, $rep);
   }
   return $matrix[$len_a][$len_b];
}

PHPにはそもそもlevenshtein()という関数があり、上記のような関数を自分で作る必要はないです。挿入コスト・置換コスト・削除コストをいろいろ変えたとき、上記関数はPHPの組込関数と結果が一致します。しかし、Wikipediaのものは一致しません。Wikipedia方式は次のような解釈と思います。

・Bからの削除によりAに近づく場合:
Bからb(i2)を削除すれば良いので、d[ i1, i2 ]はd[ i1, i2 – 1 ]にb(i2)を削除するコストを足したものに等しい。
・Aへの挿入によりBに近づく場合:
a(1)~a(i1 – 1)の文字列にb(i2)を挿入すればよいので、d[ i1, i2 ]はd[ i1 – 1, i2 ]にb(i2)を挿入するコストを足したものに等しい。
・Aの文字を置換することでBに近づく場合:
a(i1)をb(i2)に置換すればよいので、d[ i1, i2 ]はd[ i1 – 1, i2 – 1]にa(i1)を置換するコストを足したものに等しい。

この方が理解しやすいですが、両方の文字列を編集しているのでもともとの定義からは外れていると思います。ただし、たいていの場合に上記の2つの解釈は結果が一致します。というか、挿入コストと削除コストが等しい場合には同じになります。逆に言うと、コストが挿入と削除で対称でない場合は違う結果になります。
ただし、レーベンシュタイン距離が距離の公理を満たすためには挿入と削除に対して対称でなければならないため、結局どっちでもイイっていう。
あるいは基本的に私が勘違いしている可能性も高いです。

以上

Home > プログラム Archive

Search
Feeds
Meta
 合計:000242
 今日:0114 昨日:0128

Return to page top