# 今週何知った？ week:35

## 各自発表

> [name=makicamel]

## 2.1 転置インデックスの概要
- 転地インデックスのイメージ
- ドキュメントを単語に分割（これを索引語とする）し、出現位置の情報を求める
索引語を行、ドキュメント ID を列として「索引語がドキュメントに出現すれば 1、しなければ 0」とした行列が転置インデックスのイメージ
- 転置インデックスを参照することである索引語がどのドキュメントに出現しているかがわかる

<img width="416" src="https://img.esa.io/uploads/production/attachments/19215/2023/03/27/49657/4ddccfab-1010-4081-83ca-e13477e9e661.png">

[検索システム ― 実務者のための開発改善ガイドブック](https://www.lambdanote.com/collections/ir-system) - p.27

## 2.2 実用的な転置インデックスの構造
- 「索引語 - ドキュメント行列」の転置インデックスは非効率なので実用的ではない
- 実用的な転置インデックスは以下のふたつのデータ構造で構成される
- ターム辞書
- タームを並べたもの
- タームとは転置インデックスを検索する際の最小単位
- 前節でいう索引語
- ポスティングリスト
- タームが出現するドキュメントの識別子（ドキュメント ID）を格納するリスト
- タームの出現位置や文字位置などの付加情報を保持させることもある
- ターム辞書中の各タームからポスティングリストのドキュメント ID を参照できるようにしたものが実用的な転置インデックスのデータ構造

<img width="540" src="https://img.esa.io/uploads/production/attachments/19215/2023/03/27/49657/f404531f-6426-4b2c-8db5-43558f1889cb.png">

[検索システム ― 実務者のための開発改善ガイドブック](https://www.lambdanote.com/collections/ir-system) - p.29

### 2.2.1 ターム辞書のデータ構造
- 辞書順
- 二分探索で辞書引きできる
- 検索時によく用いられる
- ハッシュテーブル
- 二分探索よりも高速
- プレフィックスを指定した検索クエリのサポートが難しい
- 転置インデックス構築時によく用いられる

### 2.2.2 ポスティングリストのデータ構造
- ポスティングリストはターム辞書よりも非常に大きくなる
- 転置インデックスのファイルを書き出す際に小さなインデックス郡をまとめてひとつの大きな転置インデックスに統合する戦略が主に用いられる

## 2.3 転置インデックスを使った検索の流れ
以下の流れを `クエリ処理` と呼ぶ
1. ユーザが入力した文字列（検索クエリ）をタームに分解する（テキスト解析）
2. ターム辞書を引き、検索対象のポスティングリストを見つける（辞書引き）
3. ポスティングリストを先頭から走査してマージする（ポスティングリスト走査）
4. 見つかった検索結果をランキングして返却する（ランキング）
<img width="570" src="https://img.esa.io/uploads/production/attachments/19215/2023/04/02/49657/5e0b3e90-b4f5-4495-bd6b-c878b3378f0b.png">

### 2.3.1 テキスト解析
- 入力クエリをタームに分解する
- 検索エンジンが行う場合、検索エンジン外で行う場合の両方がある
- 類義語展開
- ドキュメントに検索文字列が含まれていたとしても、ターム辞書にないタームでは検索ができない

### 2.3.2 辞書引き
- テキスト解析で分解されたすべてのタームについてターム辞書を引き、対応するポスティングリストのエントリを見つける

### 2.3.3 ポスティングリスト走査
- 辞書引きで得たポスティングリストを頭から走査し検索結果となるドキュメントの ID を得る
- 複数のタームに対応した複数のポスティングリストが得られるので AND や OR でマージした結果を返す
- フレーズ検索やハイライト機能のための処理を行う

### 2.3.4 ランキング
- 検索クエリとドキュメントの類似度を計算し検索結果を適切な順番にソートする
- タームが個々のドキュメントに出現する回数
- タームのドキュメント全体での出現頻度

> [name=ken3ypa]

## データベースのキー種別について

### きっかけ
- 放送大学にて、データベースの授業をとったので、授業内容の陰干しをば

### キーについて
- キーとは
- 関係において、タプル（行）を一意に識別するための属性もしくは属性集合
- キーの種類
- 主キー
- 関係の中に、一つだけ設定されるキー
- 一意性制約と非NULL制約を併せ持つ
- 候補キーの中からデータ管理上最も適切であるものが選ばれる
- ナチュラルキー
- エンティティが本来持つ属性からなる主キー
- サロゲートキー
- ナチュラルキーではない主キー
- 「代わりに・代理で」付与される
- IDの連番に代表されるように、それ自体に意味はなく、一意性を確保して主キーとして使うためだけに利用される
- 留意点：
- > ・自然キー (後述) を主キーにしないことでデータが重複する (上図だと「会社コード」「商品コード」の組み合わせが重複する) 可能性が出てくるため、重複しないように別途ユニーク制約などを適切に設定する必要がある
- https://knooto.info/software-design-surrogate-key/
- 外部キー
- 他のリレーションの主キー（または候補キー）を参照する項目
- 候補キー
- 関係の中に複数存在することもある
- 主キーの候補となる
- NULLを許可する属性を持つものでも可能
- 条件
- タプルを一意に識別できる
- 極小である（スーパーキーの中で極小のもの）
- スーパーキー
- タプルを一つに特定できるもの
- 極小でなくともいい
- 候補キーにさまざまな組み合わせで他の属性を付け足したもの
- 関係の中に、候補キーの数以上に存在する
- 「極小」とは
- 属性集合の中で、余分な属性を含まず、どれか一つでも欠ければ一意性を確保できなくなる組み合わせのこと

### 参考
Railsでもナチュラルキーを主キーにしたい場合

class CreateHogeModels < ActiveRecord::Migration[6.0]
  def change
    create_table :hoge_models, id: false do |t|
      t.string :natural_key, null: false, primary_key: true
    end
  end
end

class HogeModel < ApplicationRecord
  self.primary_key = 'natural_key'
end

### 問題
- https://www.db-siken.com/kakomon/23_toku/am2_10.html
- https://www.db-siken.com/kakomon/28_haru/am2_7.html
- https://www.db-siken.com/kakomon/28_haru/am2_5.html