全文検索エンジンを作りたい、作っている人のｽﾚ

1 ：10/03/27 〜 最終レス ：12/01/11

全文検索エンジンを作りたい、作っている人のｽﾚ
いまつくってる

2 ：

2chで使えるの作ってくれ
findは有料だし

3 ：

まかせろ
リアルタイムでindexして全文検索出来るやつってこと?

4 ：

グーグルでおｋ

5 ：

定期スレ乙

6 ：

あ、俺も作ってる

7 ：

じゃあ俺も

8 ：

このスレッドは天才pンジー「アイちゃん」が
言語訓練のために立てたものです。
アイと研究員とのやり取りに利用するスレッドなので、
関係者以外は書きこまないで下さい。
　　　　　　　　　　　　　　　　　　京都大学霊長類研究所

9 ：

リアルタイムで追加可能でHDDのアクセスが少ない転置インデックスの構造ってどんなの？
下のスレが唯一参考になるんだが。
Googleデスクトップとかはどうやってるんだろ？
第20回　転置インデックスの実装（その2）
ttp://gihyo.jp/dev/serial/01/make-findspot/0020

10 ：

>>6
ブロックを拡張する方法は、やっぱり遅かった。一般のHDDではシークが
ネックになるので、極力シークしないで作るようにしたよ。
つまり、これまで作った巨大な転置インデックスはそのまま利用し、十分
小さい転置インデックスだけを書き換えるようにしていた。検索時は巨大な
インデックスと小さいインデックスの両方を検索してマージ。小さいインデックス
が大きくなってきたら、バックグラウンドで巨大インデックスとマージ（これは時間
掛かるので週1処理とか)。マージが終われば、小さいインデックスを空にする。
こんな実装してますた

11 ：

あ、上のは>>6じゃなくて、>>9へのポイントね

12 ：

>>10
すげー参考になります！さんくす！
今考えてるのは単語の出現確率であらかじめ予定サイズを割り振っておいて
最初に全体で800MBとか巨大に取ってしまって、そこに割り振る、という感じです。
（Google Desktopがそんな感じ？ぽいので）

13 ：

indexを一個にまとめなければ良いんでは。
200個くらいに分割すれば、一個5Mでも1ギガ扱える。
更新は5M程度済む。

14 ：

単語の出現位置は、差分だけ記録すれば一データを平均1バイト程度
であらわせる。
1Mあれば、100万個の位置を記録できる。

15 ：

>>13
それも考えたんだけど、結局小さいインデックスを多数用意するという事は、
シークがそれだけ増えるのであんまりパフォーマンスでなかった。
でも、RDBMSのようにテーブルスペースを定義し、複数のストレージに
同時アクセスできれば状況が違うかも知れない。少し考え方が違うけど、
H.E.　のバックエンドであるqdbmは、そういう事ができる
>>14
H.E. .なんかだと、そもそも位置情報はいらないんじゃないかという大胆な
発想だけど、>>9でもポイントされているFINDSPOTでは位置情報をあいまい
検索なんかに利用していて、バッサリ切るにはもったいない。
位置情報に限らず、転置インデックスにはデルタが必ず正の数になる数列が
色々出てくるわけで、この性質に特化した専用圧縮は、確かに効果が高い。
今、圧縮sufix arrayのイイトコドリして転置インデックスを圧縮できないか奮闘中
一応言っとくけど、自分はH.E.の中の人でも FINDSPOTの中の人でもない、ただの人です。

16 ：

1000Mのランダムアクセスと、複数ファイルへのアクセスは変わらないだろ。
シークじゃなくてファイルのopenなどが時間くう。
100個-200個程度なら開きっぱなしでいけるはず。

17 ：

>>16
うん。だからランダムアクセスはなるべく使わないようにやってみたよ。
つまり"foo"のインデックスは、1ファイルの一箇所に常にまとめる。
分散すると"foo"のインデックスを複数ファイルから検索する事になる
ので遅くなってしまうのが分散のデメリットだと思った。
だけどこれだと書き込みが出来ない（やりにくい）ので、苦肉の策で
間を取ったのが、>>10で書いた大きいのと小さいのとの2つに分散する方法

18 ：

それならfoo foe foi ・・・とhoge hage hoe・・・ などで
一ファイルずつ分けたって同じだろう。

19 ：

>>18
open()の負荷は別問題として、それならいいんじゃないの？
問題としてたのは、"foo"を数箇所から取得するという事だから。
あくまで、うちで作った実装での話しだけどね。

20 ：

追加更新での大移動を避けられるっていうこと。
一ファイルだと一部の追加だけでまるまるコピーしないといけない。

21 ：

>>20
大移動を避けるかどうかという視点だと、ファイルシステムレベルなら確かに
1-gram　1ファイルはアリのように見える。
でも、それはあくまでファイルシステムから見た場合の話しであって、ファイルが
細切れになっていると、せっかく同一ファイルの同一位置に情報を集約しても物理
的な配置がばらばらになって検索パフォーマンスは悪くなったんだよ。

22 ：

>>21
どちらにしたって断片化は防げないし
断片化しないように書き込むには毎回
領域確保して書き込まないとね

23 ：

>>22
だね
その辺は実はまだ追求が甘いんだけど、テキトーに確保したりそんな感じ
いずれにせよ、うちの実装だと大移動があるのは事実なので、そこは確かに
弱点なんだなー

24 ：

よほど断片化して無ければ速度差なんて無いだろ。
アルゴリズムでブロック単位で読みことが確定していれば別だが。

25 ：

てか、インデックスを全部メモリーに載せるのがいちばん

26 ：

専用マシーンならそれもアリだが。
デスクトップで使ってほかにもソフト動くなら占有できないが

27 ：

断片化、かなり重要だと思う。
俺のソフトでは何も考えずに後ろにぽんぽん追加してたら（転置インデックス部分じゃないけど）
10000とかに断片化していて直近のデータサーチするのが死ぬほど重くなった。
100MB単位とかで確保してしまった方がいいような希ガス。

28 ：

最近はしょちゅう再インストールしてるから
あまり断片化のことは気にしなくなったな…
扱うデータがそれほど大きくないので外に
出して管理したほうが楽だった…

29 ：

ソフトの起動と設定。インストーラの実行手順。
環境復旧までかかる手数を最小限に押さえ込む
いま必要な道具だけzip風な形式で固めておいて
展開して復旧。あとはいらないpluginの見直し(これでだいぶ軽くなる
この辺か…ｸﾗｲｱﾝﾄｻｲﾄﾞで気をつけてることは…。

30 ：

結構作ってる人居るんだな。みんな商用？
うちは商用だけど、転置インデックスそのものは自分の私物。
いつか公開したいと思ってたりするんだけど、特色ないとつまらないよな。

31 ：

個人用のデスクトップ検索エンジン、それとも小規模のサーバー型？
どっちなの？

32 ：

>個人用のデスクトップ検索エンジン、それとも小規模のサーバー型？
ん、つまりRDBMSで例えるなら自分で開発したMySQLみたいな物を
持っていて、仕事ではそれを利用してアプライアンス作ったり、WEB
サイトのバックエンドに利用したりしてるってイメージ。
だからデスクトップ用とかサーバー用とかいう以前に、ただの部分でしかないね。

33 ：

おい、>>1はどうしたんだよ？

34 ：

っしゃああああああああああ！おれもつくるどーー！！

35 ：

あげ

36 ：

ag

37 ：

　　∧,,,∧　
　( 　・∀・)　ほー　それで
　 (　　：　)　
　　し─J

38 ：

文書ファイルのサイズが2GBを超えそうだ・・・。
intの範囲も超えるし、基本データ構造から作り直さないとダメっぽい。
転置ファイルを高速化するチャンスではあるんだけど(>>10さんの方法で行く予定)
やっぱ面倒（はぁ）
と愚痴をこぼしつつ保守でした。

39 ：

作ってる人いるのか。作ってみるか。

40 ：

インデックス作成と検索のライブラリ公開してくれないかな。
自分用にインターフェース部だけ作りたい

41 ：

どんな言語用のどんなAPIのライブラリがあるといいですか？

42 ：

test

43 ：

2gramから一文字検索はどうやるんですか?
一文字を含むすべての2文字にしたら計算時間かかると思いますが。

44 ：

2gramと1gramのindex両方用意するか

45 ：

3ヶ月放置でも落ちないか・・・。保守と。

46 ：

久しぶりに覗いてみたけど、まだあったのか。
>>1は完成したのか？
>>43
>>44の方法は一見よさげだけど、占有するディスクサイズ以外に、キャッシュヒット率が
落ちるという問題があるのであまりお勧めできない。
2gramのaa~az を物理的な近傍に配置し、"a"で検索する時に一気に読み込みできるロジックがあると良いよ。

47 ：

高性能な検索順位チェックツールが今なら無料です。
http://www.kensaku-giken.com/2/904-2.htm
PCのYahoo!・Google・MSNの順位・インデックス数・被リンク数チェック
携帯のYahoo!モバイル・Googleモバイル・gooモバイルの順位・インデックス数・被リンク数チェック、
ライバルサイトのインデックス数・被リンク数のチェックなどができます。
毎日１回起動して、【検索】ボタンを押すだけで、
数百サイトの順位チェックを自動で行い、過去の検索結果も記録して残します。
SEO対策の検証に不可欠な順位・インデックス数・被リンク数の変動をチェックすることができます。
市販されている順位チェックツールは１万円以上するものばかりですが、
そのようなツールよりも高機能なのに無料です。
利用制限なども一切ありません。
PC＆モバイル対応の検索順位チェックツールです。

48 ：

「俺の全文検索」のソースをアップロードした。
http://www.ne.jp/asahi/sun/patagonia/fulltext/fulltext.html
うまく全文検索できないときには掲示板に書きこんでくれ。

49 ：

PHPだけで動くやつ作るよ

50 ：

>>48
乙。
ソースは見てないけどリアルタイムにデータの追加は可能？

51 ：

人間がリアルタイムで登録用アプリの実行させれば可能。

52 ：

PHPだけってことは、二�c的な？

53 ：

>>52
一文字単位で登録して漏れなし検索を実現する。PHPのみで。

54 ：12/01/11

ApacheのluceneかSolrでいいだろ