編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー
昨日 最長共通部分列問題 (LCS) について触れました。ついでなので編集距離のアルゴリズムについても整理してみます。 編集距離 (レーベンシュタイン距離, Levenshtein Distance) は二つの文字列の類似度 (異なり具合) を定量化するための数値です。文字の挿入/削除/置換で一方を他方に変形するための最小手順回数を数えたものが編集距離です。 例えば 伊藤直哉と伊藤直也 … 編集距離 1 伊藤直と伊藤直也 … 編集距離 1 佐藤直哉と伊藤直也 … 編集距離 2 佐藤B作と伊藤直也 … 編集距離 3 という具合です。 編集距離はスペルミスを修正するプログラムや、近似文字列照合 (検索対象の文書から入力文字にある程度近い部分文字列を探し出す全文検索) などで利用されます。 編集距離算出は動的計画法 (Dynamic Programming, DP) で計算することができることが
第11回 Kansai.pm / スペルミス修正プログラムを作ろう - naoyaのはてなダイアリー
昨日は第11回 Kansai.pm でした。 今回は無理を言って自分がホストを担当させていただきましたが、面白い発表が多く開催した自分も非常に満足でした。 PFI の吉田さんによる Cell Challenge での計算機に合わせたアルゴリズムのチューニング手法の発表 (発表資料) は圧巻でした。伊奈さんの本文抽出の話 (発表資料)、はこべさんのコルーチンの話 (発表資料)、いずれも難解になりがちなところを凄く分かりやすく解説されていて、さすがだなと思いました。各々ショートトークも、いずれも良かったです。 スペルミス修正プログラムを作ろう 自分も 20 分ほど時間をいただいて、スペルミス修正プログラムの作り方について発表しました。 スペルミス修正プログラムを作ろうView more presentations from Naoya Ito. スペルミス修正プログラムについてはずばり スペル
String::Trigram
NAME String::Trigram - Find similar strings by trigram (or 1, 2, 4, etc.-gram) method SYNOPSIS use String::Trigram; Object Oriented Interface my @cmpBase = qw(establishment establish establishes established disestablish disestablishmentarianism); my $trig = new String::Trigram(cmpBase => \@cmpBase); my $numOfSimStrings = $trig->getSimilarStrings("establishing", \%result); print "Found $numOfSimStr
Yahoo! ウェブ検索 API で単語同士の近さを総当たりで調べる
Yahoo! ウェブ検索 API で単語同士の近さを総当たりで調べる 2009-02-26-2 [Programming][YahooHacks] あらかじめ用意された単語セットがあり、それぞれの単語同士の近さを検索ヒット数とそれによるシンプソン係数で求める手順について。 使用している Web API の提供が終了となったため、現在動作しません。ご了承ください。 Yahoo!デベロッパーネットワーク (YDN) のウェブ検索 API を用いる。 - Yahoo!デベロッパーネットワーク http://developer.yahoo.co.jp/ - Yahoo!デベロッパーネットワーク - 検索 - ウェブ検索 http://developer.yahoo.co.jp/webapi/search/websearch/v1/websearch.html ロジック やってることは、下記で書かれ
Lingua::LanguageGuesser はいかにして生まれたのか
言選Webは東京大学情報基盤センター中川研究室で公開している 専門用語（キーワード）自動抽出サービスです。 このシステムは内部で、専門用語（キーワード）自動抽出Perlモジュール"TermExtract"を活用しています。 特に西欧言語版では英語だけではなく、フランス語、イタリア語などの用語抽出を行うことができます。 しかし、入力テキストがどの言語で書かれているか判定する仕組みをもたず、ユーザがその都度指定する必要がありました。 そこで、入力テキストがどの言語で書かれているか、自動判定する仕組みを新たに考えることになった次第です。 言語判定を行う方式を調べたところ、いくつかの手法があることがわかりました。 N-Gramモデルを用いたテキストの分類器を使う 各言語で頻出する単語や特徴的な単語があるかどうかで判定する アクセス先サイトのURLから国名を得る HTMLのMETAタグの記述を確認す
Text::MeCabによるN-Best解オプション指定について -OKWave
オプション指定を行ってもそのように表示されず、日本語ドキュメントも少ないため完全に嵌ってしまいました。 すぐに必要な処理でしたので、精神的に参ってしまいました。 大変お手数をお掛け致しますが、ご助言頂けないでしょうか。宜しくお願い致します。 また、5-Best出力時の以下のような各要素の格納方法なども併せて宜しくお願い致します。 ・分割要素数が多い（少ない）場合を採用する ・カナを用いて5-Best解を求める 以下、5-Best解の列挙が欲しいのに、1-Best解（通常時と同じ）しか出力されないプログラムソース。 use Text::MeCab; $nbest = 5; my $str = "アラブラブラブアブラ王"; my $m = Text::MeCab->new({nbest => $nbest}); my $n = $m->parse($
「日本語テキストを分類するベイジアンフィルタ」を簡単につくるyo - download_takeshi’s diary
数週間前の話になりますが、「はてブのリニューアル会見」の記事を読んでいたところ、はてブにも「自動カテゴライズによる記事分類」の機能が搭載されるとか。。。 同じようなタイミングで「似たようなモノ」というか「ほぼ同じようなモノ」を作っていたので、すごーくインスパイアされてしまいました。ジュワ〜。（アドレナリンの放出音） 数週間たってもいまだ興奮冷めやらぬ状態なので、今日はその件について書いてみようと思います。 Lingua::JA::Categorize - a Naive Bayes Classifier for Japanese document. http://search.cpan.org/~miki/Lingua-JA-Categorize-0.00001/ 「はてブのパクリ」ではありません。「ベイジアンによる日本語テキスト分類器」を「簡単に作る」ことを目的としたモジュールです。 も
Kazuho@Cybozu Labs: キーワード抽出モジュールを作ってみた
« IIS のログを tail -f | メイン | Lingua::JA::Summarize 0.02 » 2006年04月26日 キーワード抽出モジュールを作ってみた 一昨日、同僚の竹迫さんに、文書内からのキーワード抽出技術について教えてもらっていた時、わざわざ TF-IDF注1 用に別のコーパスを用意しなくても、MeCab だったら生起コストを辞書内に持っているんだから、それを使えばいいのではないか、という話になりました。 竹迫さんがその日のうちに作ってくれたプロトタイプで、アルゴリズムの改善とパラメータのチューニングを行ったところ、十分な品質が出そうなので、書き直して公開することにしました。 普通の Perl モジュールなので、 perl Makefile.PL && make && make install すれば使うことができます (15:50追記: すみません。 MeCab
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Algorithm-NaiveBayes-0.04 - Bayesian prediction of categories - metacpan.org