タグ

algorithmに関するn4_tのブックマーク (9)

  • [プログラミング] ビット並列アルゴリズムを使った編集距離 - 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の日記
  • 転置インデックスの圧縮 - tsubosakaの日記

    Managing Gigabytes勉強会で転置インデックスの圧縮の話が出たので実際に圧縮を行った場合にどれくらいのサイズになるかを計測してみた。 利用したデータは英語版Wikidiaの全記事で 文書数 2,872,589 単語数 2,735,620 転置インデックスのポインタの数 397,603,176 ぐらいのサイズのデータです。 無圧縮の転置インデックスのフォーマットは 単語ID,文書数,文書1,....文書N, 単語ID,...で各項目4byteとなっており、1.5Gぐらいのサイズになっています。 これに対して各圧縮アルゴリズムを適用した結果は アルゴリズム 無圧縮 Variable Byte Code unary符号 γ符号 δ符号 Rice Coding pforDelta(仮) サイズ 1537MB 497MB 239475MB 474MB 407MB 367MB 455MB

    転置インデックスの圧縮 - tsubosakaの日記
  • 統計的に正しいランキングを行う方法 - Hello, world! - s21g

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 ポジティブ/ネガティブ投票による正しいランキング方法が以下の記事で紹介されています。 How Not To Sort By Average Rating この計算方法では、投票数が少ない場合には分散が大きく不正確な評価で、 投票数が多くなるにつれて分散が小さく正確な評価が得られているという事を考慮しています。以下数式 これはScoreの信頼区間を表しています。 この信頼区間の下界をランキングのスコアにすれば良い事になります。 ここで、は、 です。全体に占めるポジティブ投票数の割合ですね。 は標準正規分布上の 信頼区間の有意確率です。 さて、五段階評価によるRatingに同様のテクニックを適用する場合はどうしたらいいでしょうか

  • Logarithmic merging - naoyaのはてなダイアリー

    IIR の第4章 Dynamic indexing では検索用のインデックスにおいて対象とする文書に頻繁に更新が発生する場合にどうそれを扱うべきかという話題を扱っています。ここで "Logarithmic merging" という話が出てきます。以前に読んだ際に良く理解できなかったので、改めて復習してみました。 Dynamic indexing 頻繁に検索対象の文書群に更新が発生する場合の問題点は、(postings ファイルはディスク上にあるので) 転置インデックスをその都度構築し直すコストが高くなってしまうというところです。かといって更新をしないと、検索結果が古いままでヒットすべきものがヒットしなくなってしまいます。そこで Dynamic indexing の戦略を採ります。ディスク上の大きなインデックスであるメインのインデックスに加えて、インメモリの小さな補助インデックスを用意し、更

    Logarithmic merging - naoyaのはてなダイアリー
  • Fenwick tree

    Fenwick tree (aka Binary indexed tree) is a data structure that maintains a sequence of elements, and is able to compute cumulative sum of any range of consecutive elements in time. Changing value of any single element needs time as well. The structure is space-efficient in the sense that it needs the same amount of storage as just a simple array of elements. The basic rule that the structure work

  • algorithm - correction - 最近点検索 : 404 Blog Not Found

    2009年04月29日07:45 カテゴリMathアルゴリズム百選 algorithm - correction - 最近点検索 これ、「素直な解答」の方が間違っている。 404 Blog Not Found:algorithm - 最近点検索 ぬじゃらだーさんのコメント このアルゴリズムって点が原点から等距離に分布している場合はまったく働かないですよね。 その通り。その一方で、「近い順にソート」は合っている。しかしこれだとO(n log n)。 TSさんのコメント もとの最近点探索の問題を解くには、点集合Pのボロノイ図データを作っておいて問い合わせに答えるのが正攻法ではないでしょうか これだと確かに高速。点がすべて格子点上にある場合(たとえばビットマップ)、ボロノイ図があらかじめ用意してある場合はO(1)で判定できる。たとえば各格子点にあらかじめどの点が一番近いかを記録しておき、それを読

    algorithm - correction - 最近点検索 : 404 Blog Not Found
  • 二次元の値(x, y)をもつ集合P から任意の点p の近似点を検索するアルゴリズムを考えています 高速、低負荷で検索するにはどうしたらいいでしょうか?…

    二次元の値(x, y)をもつ集合P から任意の点p の近似点を検索するアルゴリズムを考えています 高速、低負荷で検索するにはどうしたらいいでしょうか? 条件は次の通りです 1.集合Pはあらかじめ、任意の順番でソートしておける 2.点pの近似点にする条件は、margin範囲内で一番近いものとするが、margin値はそのときどきで変わる ターゲットの言語はjavascriptで、200msぐらいの間隔で検索を続けるつもりです 集合P の個数が 1000 ~ 10000 点くらいだったらどうしますか? みなさんのアイディアを貸してください

    n4_t
    n4_t 2009/04/19
    四分木 kd木 VP木 ボロノイ図
  • ソートアルゴリズムの可聴化 - ならば

    Sorting Algorithm Animationsなどのサイトでは、ソートアルゴリズムの可視化の例を見ることができる。今回は可視化に倣ってソートアルゴリズムを可聴化した。聴覚化すると、情報を分かりやすく提示するという方向から外れるけど。 ソートする対象は50から90までの整数をランダムに並べた列。可聴化の方法は、整数をMIDIノート番号とみなして、ソートアルゴリズムが各時点でポイントしている位置にある、MIDIノート番号の音高の音を鳴らすようにした。ChucKのプログラムはいつもより長くなったから最後に載せる。 録音したもの。元の整数列は全部同じで、サイズ(整数の数)は30。 バブルソート 選択ソート 挿入ソート シェルソート クイックソート マージソート ヒープソート 拡張としては、 より詳細に情報を提示する方向(例:整数同士の位置の交換時に音色を変える) サウンドアートな方向(例

    ソートアルゴリズムの可聴化 - ならば
  • Sorting Algorithms Animations

    KEY Black values are sorted. Gray values are unsorted. A red triangle marks the algorithm position. Dark gray values denote the current interval (shell, merge, quick). A pair of red triangles marks the left and right pointers (quick). DISCUSSIONThese pages show 8 different sorting algorithms on 4 different initial conditions. These visualizations are intended to: Show how each algorithm operates.

    Sorting Algorithms Animations
  • 1