タグ

algorithmとsearchに関するtaloのブックマーク (6)

  • [を] Dynamic Programming による類似文字列マッチの実装例

    Dynamic Programming による類似文字列マッチの実装例 2007-01-22-4 [Programming][Algorithm] 「Modern Information Retrieval」(8.6.1 p.216) での Dynamic Programming (DP) の解説のところのアルゴリズムを 素直に Perl で実装したみた。 さらにマッチ箇所取り出しロジックも実装してみた。 DP はいわゆる「類似文字列検索(あいまい検索)」に使うと 便利なアルゴリズム。 実は、大学院でも前の会社でも、PerlやらC++やらで実装して使ってた。 単純ながら使い勝手もよく、まさに現場向きかと。 grep 式に頭から見ていくので計算量的にはイマイチなのだが、 転置インデックス検索などで範囲を絞ってから適用すれば実用上問題ない。 ■定義みたいなの Q1. 二

  • suffix array

    更新履歴 2004/01/07  O(N) 構築アルゴリズム三種追加(Ko &Alulu, Kim & al., Karkkainen & Sanders) Suffix Arrayは、最近注目を集めているデータ構造です。その理由として、 (1)大規模なデータに対して、高速に検索、情報抽出を行うことができる (2)BWTとしてデータ圧縮に用いることができる。 ことが挙げられます。(1)に関しては自然言語処理において、膨大な量のコーパスから情報(例えば、単語の出現回数など)を調べるときににSuffix Arrayを用いると非常に高速に求めることができます。 膨大な量のコーパスに基づいた自然言語処理が盛んになってきている今、Suffix Arrayが注目を集めています。 また、ゲノム情報を調べるバイオインフォマティクスにおいても、ここの配列と似ている部分(例えばCCAG)を調べるといった場合

    talo
    talo 2006/10/07
    suffix=接尾辞
  • http://www.yl.is.s.u-tokyo.ac.jp/surveyBBS2/ocamlbbs.cgi?thid=2003714145123

    talo
    talo 2006/01/29
    P2P型検索エンジンの実現可能性についての論文
  • 神戸市須磨区のトイレつまり修理【1,200円〜】水道局指定業者の水協

    弊社は神戸市須磨区水道局より認定を受けた水道局指定業者ですので安心してご相談ください。トイレや排水溝などのつまりや水漏れなど、あらゆる水回りのトラブルに適切に対応させていただきます。 1200円〜の業界最安値水準の低価格で修理対応しております。もちろんトラブルの原因によって価格は異なりますが、神戸市須磨区内のお宅ではまずは無料出張で現地を確認、無料でお見積もりをご提出させていただきます。その際に価格やサービス内容にご納得いただけずお断りいただいた場合は一切費用はかかりませんので、まずはお気軽にご相談ください。

    talo
    talo 2006/01/26
    Suffix Array
  • 横着プログラミング 第6回: chatty: 小うるさい端末

    最終更新日: 2002-09-18 (公開日: 2002-09-18) Unix Magazine 誌に 2002年1月号から 2003年2月号にかけて連載し ていた記事の元の原稿です。 才気に富んだことは個人が行うのが通例であり、信じがたきバカ さ加減は大抵組織に帰されるものである。 -- Jon Bentley *1 役に立たないソフトウェアを作るのが好きだ。面倒な作業を楽にす る横着ソフトウェアもいいが、たまには人を呆れさせるくだらない ソフトウェアを作るのも楽しい。 以前に私が開発した cdbiff*2というソフト ウェアは、メールが届くと PC の CD-ROMドライブが開いてメール の到着を通知するという役に立たないものであったが、そのくだら なさが受けて予想外の好評を得た。今回は、そうした役に立たない ソフトウェアの 1つである、小うるさい端末 chatty*3 を紹介する。

  • Dominic Giampaolo's Home Page

    I'm Dominic Giampaolo. I program computers for a living. For a long time I lived in Silicon Valley but now reside in Maine. I've worked for a number of different computer companies over the years: SGI, Be Inc., Google (briefly), and QNX. I started at Apple in 2002 and am still there. One of my claims to fame is writing the Be File System. I also wrote a book about BFS called, "Practical File Syste

  • 1