本連載の第5回でN-gramのしくみを解説しました。この中で転置インデックスは,
転置インデックス
転置インデックスは特定の見出し語に対して,
表1 転置インデックスから得られる文書IDと出現位置の集合
文書ID | 出現位置 |
---|---|
10 | 2034 |
11 | 178 |
15 | 449 |
15 : : : |
689 : : : |
連載の第2回で紹介したように,
表2 SQLによるインデックス表現
見出し語 | 文書ID | 出現位置 |
---|---|---|
今日 | 1 | 0 |
日は | 1 | 1 |
は良 | 1 | 2 |
良い | 1 | 3 |
い天 | 1 | 4 |
天気 : : : |
1 : : : |
5 : : : |
上記の表2のようなテーブルを作っておき,
リスト
select 文書ID, 出現位置 from index_table where 見出し語="今日";
ところが,
実用的な検索スピードを実現するには,
表3 転置インデックス
見出し語 | 文書ID | 出現位置 |
---|---|---|
今日 | 1 | 0 |
今日 | 3 | 238 |
今日 | 43 | 79 |
今日 | 55 | 91 |
今日 | 81 | 125 |
今日 | 90 | 23 |
日は | 1 | 1 |
日は | 3 | 239 |
日は | 22 | 85 |
日は | 38 | 23 |
日は : : : |
47 : : : |
144 : : : |
先ほどの表2のデータが文書ID順だったのに対して,