[プログラミング] ビット並列アルゴリズムを使った編集距離 - tsubosakaの日記
ふと、ビット並列アルゴリズムを使った編集距離を計算するアルゴリズムを書きたくなったので書いてみた。 まず、通常の編集距離であるLevenshtein Distanceを求めるアルゴリズムは以下のように書ける int levenshteinDistance(String A, String B) { int m = A.length(); int n = B.length(); int dp[] = new int[n + 1]; int next[] = new int[n + 1]; for (int i = 0; i <= n; i++) dp[i] = i; for (int i = 1; i <= m; i++) { next[0] = i; for (int j = 1; j <= n; j++) { if (A.charAt(i - 1) == B.charAt(j - 1))
![[プログラミング] ビット並列アルゴリズムを使った編集距離 - tsubosakaの日記](https://cdn-ak-scissors.b.st-hatena.com/image/square/7ca3ca3d9a967967d3c1900062079765c7d58c98/height=288;version=1;width=512/https%3A%2F%2Fcdn.image.st-hatena.com%2Fimage%2Fscale%2F3b21b9940827376b8faf757c1dcc041507e62d8d%2Fbackend%3Dimagemagick%3Bversion%3D1%3Bwidth%3D1300%2Fhttps%253A%252F%252Fcdn-ak.f.st-hatena.com%252Fimages%252Ffotolife%252Ft%252Ftsubosaka%252F20091103%252F20091103000001.jpg)
naoyaのはてなダイアリー
ときどき、たまたま自分がそのとき考えていたことについてそれを補強するような材料が偶然たくさん集まってくる、なんてことがあります。そんな出来事があったので、ちょっとブログを書いてみようかなと。 以前に HBFav を作ったときこんなことを書きました。 Mark Zuckerberg は、いずれみんな、ニュースは友人知人経由で知ることになるだろうと言っていました。自分もそうなるだろうと思います。 4年ぐらいが経ちましたが、その思いは以前よりも増して確信めいたものになってきています。 ところで先日、Twitter の iOS アプリに「ニュース」という機能が追加されました。人によっては出てないそうなのでまだテスト中か、もしくは既に削除されているのかもしれないですが。 この機能についての自分の感想は以下のようなものでした。 もうすこし補足します*1。 Facebook や Twitter のような
DO++ : 透過的データ圧縮
可逆データ圧縮分野で、現在研究が盛んな分野の一つが、データを圧縮した状態のまま定数時間でランダムアクセスをサポートするデータ圧縮方式です（word RAMモデルでO(log n)サイズの復元が定数時間)。 これは、データをあたかも圧縮していないかのように扱えるため、透過的データ圧縮/構造と呼ばれています（英語だとまだ決まってない？)。 例えば1GBのデータを圧縮した状態で、途中300MB目から4Byteだけ復元しようというのが定数時間で実現できるわけです。これは理論的にもかなり強いことをいっていて，例えば今あるデータ構造やアルゴリズムが、O(T)時間である問題を解けるというのがあったら、それを全く同じO(T)時間のままデータ構造を圧縮し作業領域量を減らすことができます (一応データ構造に対し読み込み操作しか無い場合。書き込みもある場合はまたちょっと面倒になる） このデータを圧縮したまま扱う
Information Knowledge Network Special Lecture / IKN Laboratory
Lecture / 授業 Information Knowledge Network Special Lecture 情報知識ネットワーク特論 Semester / 開講 Tuesday, 3rd hour (13:00-14:30), Winter, Graduate School of IST, Hokkaido University 後期火３限, 大学院情報科学研究科，北海道大学 The URL of this page: http://www-ikn.ist.hokudai.ac.jp/ikn-tokuron/ News / 新着情報 Updated on 30 Nov. 2016. Description of This Lecture / この授業の説明 Purpose / 目的 情報検索とデータマイニングについて，基本的な考え方とアルゴリズムを学びます. Learning b
検索アルゴリズム (4)文字列の検索 -2-
検索アルゴリズム (4)文字列の検索 -2- 前章に引き続き文字列照合(string matching)のアルゴリズムから、この章ではBoyer-Moore(BM)法を紹介したいと思います。このアルゴリズムは、実用上最速な文字列照合アルゴリズムとして文字列検索ツールやエディタで使用されているようです。 1)BM法 BoyerとMoore、また両者とは別にGosperが考案したBoyer-Moore(BM)法の最大の特徴は、パターンを末尾側から逆方向に比較するということです。 テキストとパターンの先頭をそろえた後、今までのアルゴリズムではパターン先頭とテキスト先頭を比較するのですが、BM法ではパターン末尾(先頭からm文字目)の文字と、テキストのm文字目の文字を比較します。もし一致していたら注目文字を1つ前にずらし、末尾側から逆方向に比較していきます。もし不一致が検出されたら、不一致を引き起
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
サービス終了のお知らせ
