マルコフ連鎖を使って作曲する試み。 文章にしろ曲にしろ、マルコフ連鎖を使って何かを生成する場合、マルコフ連鎖自体、つまり状態と遷移確率行列に相当するデータを準備する必要がある。このデータが最終的な出力の質のかなりの部分を左右する。このデータを準備すれば、生成の部分は特に凝ったことをしない限り、サイコロを転がす程度のことで済む。 実際にある文章や曲を元にデータを作ろうと思うと、状態の切り出しが難しい場合がある。英語の文章の場合は、最初から単語で分かち書きされているから楽だ。日本語の文章の場合は、形態素を状態とすると、状態の切り出しはMeCabなどの形態素解析プログラムに任せることができる。曲の場合は、多分今のところ簡単で汎用的な方法はない。本格的に研究するなら用意した曲の音響分析をしたりするのかもしれないけど、音響分析なんて全然知らないし、今回は実際にある曲を元にデータを作るつもりでも気軽に

11000ステップ経ったラングトンのアリ。赤い点のところにアリがいる。 ラングトンのアリ（英: Langton's ant）は、クリストファー・ラングトンが発明した単純な規則で記述される2次元チューリングマシンである。 ラングトンのアリが200ステップ移動するまでのアニメーション 平面が格子状に構成され、各マスが白または黒で塗られる。ここで、1つのマスを「アリ」とする。アリは各ステップで前後左右のいずれかのマスに移動することができる。アリは以下の規則に従って移動する。 白いマスにアリがいた場合、90°右に方向転換し、そのマスの色を反転させ、1マス前進する。 黒いマスにアリがいた場合、90°左に方向転換し、そのマスの色を反転させ、1マス前進する。 この単純な規則で驚くほど複雑な動作をする。当初でたらめな動作をしているが、アリはいずれ例外なく10000歩ほどうろついた後に真っ直ぐな「道」を作る

MonaTweeta II Preliminary result of a little competition between me and Ralph Hauwert (who had the initial idea) with the goal to write an image encoder/decoder that allows to send an image in a tweet. The image on the left is what I currently manage to send in 140 characters via twitter. This is the tweet for the image: 圑嘌婂搒孵怤實恄幖戰怴搝愩娻屗奊唀唭嚟帧啜徠山峔巰喜圂嗊埯廇嗕患嚵幇墥彫壛嶂壋悟声喿墰廚埽崙嫖嘵奰恛嬂啷婕媸姴嚥娐嗪嫤圣峈嬻尤囮愰啴屽嶍屽嶰寂喿嶐唥帑尸庠

昨日 最長共通部分列問題 (LCS) について触れました。ついでなので編集距離のアルゴリズムについても整理してみます。 編集距離 (レーベンシュタイン距離, Levenshtein Distance) は二つの文字列の類似度 (異なり具合) を定量化するための数値です。文字の挿入/削除/置換で一方を他方に変形するための最小手順回数を数えたものが編集距離です。 例えば 伊藤直哉と伊藤直也 … 編集距離 1 伊藤直と伊藤直也 … 編集距離 1 佐藤直哉と伊藤直也 … 編集距離 2 佐藤B作と伊藤直也 … 編集距離 3 という具合です。 編集距離はスペルミスを修正するプログラムや、近似文字列照合 (検索対象の文書から入力文字にある程度近い部分文字列を探し出す全文検索) などで利用されます。 編集距離算出は動的計画法 (Dynamic Programming, DP) で計算することができることが

A webcomic of romance, sarcasm, math, and language. Special 10th anniversary edition of WHAT IF?—revised and annotated with brand-new illustrations and answers to important questions you never thought to ask—coming from November 2024. Preorder here!

By Evan Miller February 6, 2009 (Changes) Translations: Dutch  Estonian  German  Russian  Ukrainian PROBLEM: You are a web programmer. You have users. Your users rate stuff on your site. You want to put the highest-rated stuff at the top and lowest-rated at the bottom. You need some sort of “score” to sort by. WRONG SOLUTION #1: Score = (Positive ratings) − (Negative ratings) Why it is wrong: Supp

Use of triangular fractals to create a mountainous terrain. A fractal landscape or fractal surface is generated using a stochastic algorithm designed to produce fractal behavior that mimics the appearance of natural terrain. In other words, the surface resulting from the procedure is not a deterministic, but rather a random surface that exhibits fractal behavior.[1] Many natural phenomena exhibit

転置インデックスによる検索システムを作ってみよう！ 2007-11-26-5 [Algorithm][Programming] 転置インデックス[2007-06-17-6]による検索システムの実装は パフォーマンスを無視すれば意外と簡単です。 それを示すために Perl で簡単な検索システムを作ってみました。 検索方式は転置インデックス(Inverted Index)、 ランキングには TF-IDF[2005-10-12-1] を用いました。 検索対象ファイルは一行一記事で以下のフォーマットとします。 [記事ID][SPC][記事内容]\n 記事IDは数字、記事内容は UTF-8 の文字で構成されるものとします。 以下のようなサンプル test.txt を用意しました。 1 これはペンです 2 最近はどうですか？ 3 ペンギン大好き 4 こんにちは。いかがおすごしですか？ 5 ここ最近疲れ