以下来自维基百科:
倒排索引(Inverted index),也常被称为反向索引、置入档案或反向档案,是一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构。
有两种不同的反向索引形式:
- 一条记录的水平反向索引(或者反向档案索引)包含每个引用单词的文档的列表。
- 一个单词的水平反向索引(或者完全反向索引)又包含每个单词在一个文档中的位置。
- T0 =
"it is what it is"
- T1 =
"what is it"
- T2 =
"it is a banana"
我们就能得到下面的反向文件索引:
"a": {2}
"banana": {2}
"is": {0, 1, 2}
"it": {0, 1, 2}
"what": {0, 1}
检索的条件"what"
, "is"
和 "it"
将对应这个集合:
对相同的文字,我们得到后面这些完全反向索引,有文档数量和当前查询的单词结果组成的的成对数据。 同样,文档数量和当前查询的单词结果都从零开始。所以,"banana": {(2, 3)} 就是说 "banana"在第三个文档里 (T2),而且在第三个文档的位置是第四个单词(地址为 3)。
"a": {(2, 2)}
"banana": {(2, 3)}
"is": {(0, 1), (0, 4), (1, 1), (2, 1)}
"it": {(0, 0), (0, 3), (1, 2), (2, 0)}
"what": {(0, 2), (1, 0)}
如果我们执行短语搜索"what is it"
我们得到这个短语的全部单词各自的结果所在文档为文档0和文档1。但是这个短语检索的连续的条件仅仅在文档1得到。
-------------------------------------------------------
为什么要提出这样一种索引方式呢?
举个例子,如果有两个文档,doc1 & doc2 内容分别如下:
Doc1: it is what it is
.
Doc2: what is it
.
正向索引建立:
文档名 关键字 次数
Doc1 it 2
Doc1 is 2
Doc1 what 1
Doc2 what 1
Doc2 is 1
Doc2 it 1
不难发现,对于单文档内部检索,正向索引的建立,可以保证快速的进行检索。但对于全文检索,却很难有很好的性能,甚至由于实际资源的限制,而不可行。
“正向索引的查询往往满足每个文档有序频繁的全文查询和每个单词在校验文档中的验证这样的查询。”
题外话:
在设计某个问题的解决方案时,可能自身由于一直深入于整个工作,对问题的理解越来越深,不断有新的思路出来,继续不断有些方案出来,从来最终形成了整个解决方案。但或许,在整个过程中的某个时刻,跳出来,可能会有更高效的方法。比方说,可以参照算法方法论,如动态规划、贪心算法等来进行具体方案的求解。
Keywords: Inverted index; full-text search
18 comments:
interesting...
さあ、今夏も新たな出会いを経験してみませんか?当サイトは円助交際の逆、つまり女性が男性を円助する『逆円助交際』を提供します。逆円交際を未経験の方でも気軽に遊べる大人のマッチングシステムです。年齢上限・容姿・経験一切問いません。男性の方は無料で登録して頂けます。貴方も新たな出会いを経験してみませんか
みんなの精神年齢を測定できる、メンタル年齢チェッカーで秘められた年齢がズバリわかっちゃう!かわいいあの子も実は精神年齢オバサンということも…合コンや話のネタに一度チャレンジしてみよう
最近仕事ばかりで毎日退屈してます。そろそろ恋人欲しいです☆もう夏だし海とか行きたいな♪ k.c.0720@docomo.ne.jp 連絡待ってるよ☆
最近TVや雑誌で紹介されている家出掲示板では、全国各地のネットカフェ等を泊り歩いている家出娘のメッセージが多数書き込みされています。彼女たちはお金がないので掲示板で知り合った男性の家にでもすぐに泊まりに行くようです。あなたも書き込みに返事を返してみませんか
あなたの性格を、動物に例えて占っちゃいます。もしかしたらこんな動物かも!?動物占いをうまく使って、楽しい人間関係を築いてください
家出中の女性や泊まる所が無い女性達がネットカフェなどで、飲み放題のドリンクで空腹を満たす生活を送っています。当サイトはそんな女性達をサポートしたいという人たちと困っている女性たちの為のサイトです
セレブ女性との割り切りお付き合いで大金を稼いでみませんか?女性に癒しと快楽、男性に謝礼とお互い満たしあえる当サイト、セレブラブはあなたの登録をお待ちしております。
夏フェス一緒に行ってくれる人募集!!夏の思い出一緒につくろぉ☆ megumi-0830@docomo.ne.jp 連絡してね♪
あなたのゲーマー度を無料ゲーム感覚で測定します。15個の質問に答えるだけの簡単測定で一度遊んでみませんか?ゲームが得意な人もそうでない人もぜひどうぞ。
Hな女性たちは素人ホストを自宅やホテルに呼び、ひとときの癒しを求めていらっしゃいます。当サイトでは男性ホスト様の人員が不足しており、一日3~4人の女性の相手をするホストもおられます。興味を持たれた方は当サイトにぜひお越しください
実は出会い系には…関係者用入り口があるのを知っていますか?広告主やスポンサー用に用意されたIDではサクラや業者が立ち入ることが出来ないようになっているのです。当サイトでは極秘に入手した関係者用URLが公開されています
男性はお金、女性は快楽を得る逆援助に興味はありませんか?お金を払っても性的欲求を満たしたいセレブ達との割り切り1日のお付き合いで当サイトでは大金を得ることができます。無料登録なのでアルバイト感覚でOK、詳しくはTOPページでどうぞ。
ホムペ完成記念!私の事みんなに知ってもらいたくて頑張りましたぁ。色々とご感想をお待ちしているので思った事を意見してください。メアドはほむぺにのせてありますぅ!★ fan.jna@docomo.ne.jp
夏休みで気軽に家出する女子○生が急増しています。しかし家出したはいいものの泊る所やお金が無い彼女たちは、掲示板などで泊めてくれる男性を探す子も多いようです。当掲示板にも夏休みに入ってから通常の3倍以上のメッセージが寄せられています
今最もアツイバイトは人妻とのセフレ契約です。当サイトではお金を払ってでもセフレがほしい人妻が集まり、男性会員様との逆援生活を待っています。当サイトで欲求不満の女性との出会いをしてみませんか
素人ホストでは、男性のテクニック次第で女性会員様から高額な謝礼がもらえます。欲求不満な人妻や、男性と出会いが無い女性達が当サイトで男性を求めていらっしゃいます。興味のある方はTOPページからどうぞ
少し魅惑な自分をネットだから公開してみました。普段言えない事など、思い切って告白しているプロフなので興味ある方はぜひ除いてみてください連絡待ってまぁす。 hinyaaaaa@docomo.ne.jp
Post a Comment