【人力検索】圧縮されたデータを高速に検索するアルゴリズム【類似検索】 ふと気になったので、調べ物をお願いします。…
【人力検索】圧縮されたデータを高速に検索するアルゴリズム【類似検索】 ふと気になったので、調べ物をお願いします。 圧縮されたデータを対象に検索を行うアルゴリズムで 下記のようなもので、目ぼしい成果を上げているものを探してください。 （人力検索としては、次の類似を検索する形になります。） [PPT] 高速検索可能なテキスト圧縮法に関する研究 （復号処理を行わずに高速に検索を行う圧縮法の研究） www.tkl.iis.u-tokyo.ac.jp/~otsuka/profile/kenkyu3.ppt くどく補足しますが、「検索インデックスを圧縮することにより高速に検索が行えるようになりました」という種類のものを紹介する回答は不要です。 「gzipで圧縮されたファイルを、自動的に解凍して検索できます」という類のソフトの紹介も不要です。 上に挙げたものそのものも不要です。 ※ 探すのは難しいかもし
Não Aqui! » SimString (類似文字列検索ライブラリ) 1.0 released
SimStringという類似文字列検索ライブラリをBSDライセンスでリリースしました．類似文字列検索とは，文字列集合（データベース）の中から，クエリ文字列と似ているものを見つけ出す処理です．コンピュータは，正確に一致する文字列を探すのは得意ですが，表記揺れに出くわすと，途端に対応できなくなります．例えば，「スパゲティ」に対して，レストラン情報などを返すサービスにおいて，「スパゲッティ」や「スパゲティー」などの表記揺れが検索クエリに与えられると，通常のデータベースでは情報を提示することが出来ません．類似文字列検索を用いると，表記揺れが検索クエリに与えられても，「スパゲティ」という既知語を代替クエリとして提案したり，「スパゲティ」の情報をダイレクトに引き出すことができるようになります． 似てる語を探す技術って，文字列処理の基本中の基本で，自然言語処理では当たり前のように使われていてもおかしくな
[プログラミング] ビット並列アルゴリズムを使った編集距離 - 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/abb310b76b915a8d5d10199b4b0f5418555a807c/height=288;version=1;width=512/https%3A%2F%2Fcdn-ak.f.st-hatena.com%2Fimages%2Ffotolife%2Ft%2Ftsubosaka%2F20091103%2F20091103000001.jpg)
naoyaのはてなダイアリー
ときどき、たまたま自分がそのとき考えていたことについてそれを補強するような材料が偶然たくさん集まってくる、なんてことがあります。そんな出来事があったので、ちょっとブログを書いてみようかなと。 以前に HBFav を作ったときこんなことを書きました。 Mark Zuckerberg は、いずれみんな、ニュースは友人知人経由で知ることになるだろうと言っていました。自分もそうなるだろうと思います。 4年ぐらいが経ちましたが、その思いは以前よりも増して確信めいたものになってきています。 ところで先日、Twitter の iOS アプリに「ニュース」という機能が追加されました。人によっては出てないそうなのでまだテスト中か、もしくは既に削除されているのかもしれないですが。 この機能についての自分の感想は以下のようなものでした。 もうすこし補足します*1。 Facebook や Twitter のような
DO++ : 透過的データ圧縮
可逆データ圧縮分野で、現在研究が盛んな分野の一つが、データを圧縮した状態のまま定数時間でランダムアクセスをサポートするデータ圧縮方式です（word RAMモデルでO(log n)サイズの復元が定数時間)。 これは、データをあたかも圧縮していないかのように扱えるため、透過的データ圧縮/構造と呼ばれています（英語だとまだ決まってない？)。 例えば1GBのデータを圧縮した状態で、途中300MB目から4Byteだけ復元しようというのが定数時間で実現できるわけです。これは理論的にもかなり強いことをいっていて，例えば今あるデータ構造やアルゴリズムが、O(T)時間である問題を解けるというのがあったら、それを全く同じO(T)時間のままデータ構造を圧縮し作業領域量を減らすことができます (一応データ構造に対し読み込み操作しか無い場合。書き込みもある場合はまたちょっと面倒になる） このデータを圧縮したまま扱う
String-searching algorithm - Wikipedia
In computer science, string-searching algorithms, sometimes called string-matching algorithms, are an important class of string algorithms that try to find a place where one or several strings (also called patterns) are found within a larger string or text. A basic example of string searching is when the pattern and the searched text are arrays of elements of an alphabet (finite set) Σ. Σ may be a
String Similarity Metrics for Information Integration
Web Intelligence, Natural Language Processing Group, Department of Computer Science, University of Sheffield, Regent Court, 211 Portobello Street, Sheffield, S1 4DP, UNITED KINGDOM Tel:+44(0)114-2228000 Fax:+44(0)114-22.21810 sam@dcs.shef.ac.uk Reverend Sam Chapman's HomePage details his work at the Department of Computer Science Regent Court 211 Portobello Street Sheffield S1 4DP
Pattern Matching Pointers (maintained by Stefano Lonardi)
Combinatorial Pattern Matching addresses issues of searching and matching strings and more complicated patterns such as trees, regular expressions, graphs, point sets, and arrays. The goal is to derive non-trivial combinatorial properties for such structures and then to exploit these properties in order to achieve improved performance for the corresponding computational problem. A steady flow of h
ラビン-カープ文字列検索アルゴリズム - Wikipedia
ラビン-カープ文字列検索アルゴリズム（英: Rabin-Karp string search algorithm）は、マイケル・ラビンとリチャード・カープが開発した、ハッシュ関数を利用してテキストからパターン（サブ文字列）を探す文字列検索アルゴリズムの一種[1][2]。1つのパターンの検索にはあまり用いられないが、理論的には重要であり、複数パターンの検索には効果的である。テキストの文字数が n、パターンの文字数が m とした場合、平均および最良の実行時間はO(n)だが、ごくまれに最悪性能として O(nm)となる（広く用いられないのはそのため）。しかし、k個の文字列のいずれかにマッチする部分を検索するのに要する時間は k によらず平均で O(n) となるという独特の利点を持つ。以下、単にラビン-カープまたはラビン-カープ法と略記することがある。 ラビン-カープの単純な応用例として、盗作の検出
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ページを開く
https://www.bic.kyoto-u.ac.jp/takutsu/members/takutsu/japanese.html
Text Algorithms
Text algorithms
サービス終了のお知らせ
ESMAJ