はじめに
メモにあった単語は覚えていても、保存先のディレクトリを思い出せないことがあります。役立つ検索ツールには、一致するすべてのメモを見つけ、同名ファイルを区別し、原文で確認できる実際の行を表示する機能が必要です。
C++ の map と set でこの関係を作ります。読み込み、単語の解析、クエリ処理、行の表示は準備済みです。索引を実装し、内容を変えた練習用メモで試します。基本的なターミナル操作、C++ の文字列、vector、関数、ファイルストリーム、例外の知識が前提です。map と set はここで学びます。50 分は作成者による所要時間の見積もりです。
単語を一致するすべてのメモに結び付ける
このステップでは動作するサンプルを使い、自分の実行ファイルに単語と文書の索引を実装します。このコースでは一貫して Terminal タブを使ってください。UTF-8 のシェルが開きます。WebIDE 内のターミナルではなく、この名前のタブを使います。作業ディレクトリは接続が開いている間保たれます。別の接続を開いたら、本文の cd をもう一度実行してください。
cd は作業ディレクトリを変更します。準備済みのプロジェクトから始めます。
cd /home/labex/project/note-search
notes/reference は保護された原本、notes/practice は書き込み可能なコピーを格納します。find はパスを再帰的に列挙し、-type f は通常のファイルに限定します。表示順は重要ではありません。
find notes -type f
notes/reference/archive/notes.txt と notes/reference/field/notes.txt の両方があります。末尾の名前、つまりベース名は同じでも、完全なパスが異なる文書を識別します。./ は現在のディレクトリにある実行ファイルを起動します。完成済みの sample にはメモのディレクトリとクエリを渡します。
./sample notes cat
文書が 3 グループ返され、そのうち 2 グループは次のとおりです。
File: reference/archive/notes.txt
1: CAT, cat!
3: cat blue together
File: reference/field/notes.txt
1: cat; red
3 番目は practice/旅行 notes.txt です。識別子は渡した notes ルートからの相対パスなので、notes/ は含みません。単語が何度あっても文書は 1 回だけ現れます。数字は 1 から始まる実際の原文行番号です。関係する行だけが表示され、番号が抜けていても原文が削除されたわけではありません。比較のため cat でテキストファイルを表示します。
cat notes/reference/archive/notes.txt
2 行目の Blue ledger — 東京 は存在しますが、cat を含みません。元の UTF-8 パスと行のテキストはそのまま保たれます。
このコースの小さな単語規則は厳密です。トークンは ASCII 英字 A-Z または a-z が連続する最大の範囲で、ASCII 大文字は小文字に変換します。数字、アンダースコア、句読点、空白、および各非 ASCII バイトがトークンを区切ります。CAT-blue_42 は cat と blue、cat は catalog とは別、猫cat狗 は cat を含み、café は cafe ではなく caf になります。Unicode テキストを保つことと、あらゆる言語の単語を理解することは別です。多言語の単語分割は実装しません。
準備済みのインターフェースと開始コードを読みます。
cat search.hpp
cat engine.cpp
Document は完全な相対パスである id と、原文行の文字列を格納した vector である lines を持ちます。準備済みの読み込み処理は通常の .txt ファイルを再帰的に読み、その識別子をソートします。メモは LF 改行の UTF-8 テキストです。パスには空白や Unicode を使えますが、パス内のタブや改行、シンボリックリンク、NUL データ、任意のバイナリファイルは対象外です。読めない入力にはエラーを返し、部分的な結果は返しません。
Index は std::map<std::string, std::set<std::string>> の別名です。map は異なる単語キーそれぞれに値を対応させます。ここでの値は文書識別子の集合です。set は各識別子を 1 回だけ保持します。そのため、1 文書に cat が 3 回出ても関係は 1 つです。単語から文書を逆引きするこの構造を転置インデックスと呼びます。
開始コードは空の索引を返します。provided.inc には、この単元ですでに動くクエリ関数が入っています。#include はコンパイル時にファイルを取り込みます。search.hpp、provided.inc、support.cpp、main.cpp、sample、および notes/reference/ の全パスと内容を維持してください。編集するのは engine.cpp で、補助関数や同等のアルゴリズムを使えます。編集、追加、削除できるデータは notes/practice/ だけです。その初期ファイル構成を維持することは採点条件ではありません。
bash で準備済みの自己チェックを実行します。index はここで学ぶ動作を選びます。最初は意図的に FAIL exact whole-word postings retain complete document identities と表示して、ゼロ以外の終了ステータスになります。索引が未完成という意味で、環境の故障ではありません。
bash /opt/labex-note-search/check.sh index
各文書、各行、解析済みの各単語をたどります。範囲ベースの for は各要素を巡り、const auto& はコピーせず読み取り専用の参照を使います。index[word] はその単語に対応する文書識別子の集合にアクセスし、新しいキーなら空集合を作ります。.insert(doc.id) は完全な識別子を追加し、重複する関係を無視します。すべての文書の関係を蓄積できるよう、map を全ループの外に置きます。
次のコマンドは engine.cpp だけを置き換えます。ヒアドキュメントは複数行を cat に渡し、> は指定ファイルの内容を置き換えて書き込みます。引用した区切り 'CPP' は C++ テキストのシェル展開を防ぎます。最後の CPP は単独の行に置きます。宣言と準備済みのクエリ実装を使えるよう、2 つの include を残してください。
cat > engine.cpp <<'CPP'
#include "search.hpp"
#include "provided.inc"
Index buildIndex(const std::vector<Document>& documents) {
Index index;
for (const auto& doc : documents) {
for (const auto& line : doc.lines) {
for (const auto& word : words(line)) {
index[word].insert(doc.id);
}
}
}
return index;
}
CPP
words(line) は準備済みの ASCII パーサーです。ベース名だけを取り出したり、最初の一致で止めたり、文書集合の代わりに出現回数を保存したりしないでください。
成果物をコンパイルします。g++ はコンパイラー、-std=c++17 は言語版の選択、-Wall -Wextra は有用な警告の有効化、-o findnotes は出力実行ファイルの命名です。3 つの .cpp は、自分の検索エンジン、準備済みの読み込みと解析、コマンドインターフェースです。include したファイルは自動的に読み込まれます。
g++ -std=c++17 -Wall -Wextra engine.cpp support.cpp main.cpp -o findnotes
ビルド成功時は通常何も表示されません。エラー時は最初のファイル名と行番号を読み、engine.cpp を修正するか全体の置換をやり直し、再コンパイルします。失敗後に古い実行ファイルが残る場合があります。ソースの編集だけでは更新されません。自己チェックは隔離したデータ上で自分の関数をそのまま実行し、既存の findnotes も試します。実行ファイルを代わりに再ビルドすることはありません。
./findnotes notes cat
サンプルと同じ 3 つの文書識別子と原文行が出るはずです。再現可能なら別の文書順も許されますが、文書内の行番号は昇順で各行 1 回だけです。このステップは索引と単語 1 個の検索を採点します。異なる検索語の組み合わせは今は準備済みで、次のラボで自分の課題になります。
現在の練習メモから索引を作り直す
このステップでは原本を保ちながら、練習データを編集、追加、削除します。Terminal の /home/labex/project/note-search に留まります。起動するたびに現在のファイルを読み、新しいメモリ内索引を作ります。保存済みの索引ファイル、更新用デーモン、追加の再構築コマンドはありません。
まず完全な単語の境界を比べます。
./findnotes notes catalog
catalog を含む行とともに、reference/catalog.txt と practice/旅行 notes.txt が出ます。これらは追加の cat の一致ではありません。未知の単語も正常な検索です。
./findnotes notes absent
No matching documents. と表示して正常終了します。準備済みのインターフェースが拒否する不正な入力とは異なります。次のラボでこの違いを調べます。
練習用コピーはすでに書き込み可能で、参照原本は読み取り専用です。単一引用符は空白を含むパスを 1 引数に保ち、Unicode 文字を維持します。printf はテキストを出力し、\n は改行を作ります。> は指定練習ファイル全体を置き換えます。このコピーに cat がなくなるよう内容を置換します。
printf 'owl green\n東京 — preserved\n' > 'notes/practice/旅行 notes.txt'
./findnotes notes cat
一致するのは参照メモ 2 つだけになりました。練習ファイルは存在しますが、現在の内容では一致しません。許可された練習メモをもう 1 つ追加します。
printf 'CAT beside the window\nA new observation\n' > 'notes/practice/new notes.txt'
./findnotes notes cat
practice/new notes.txt の 1 行目を含め、再び 3 文書が一致します。再コンパイルはしていません。データを変えたら再実行するだけでよく、C++ ソースの変更にはコンパイルが必要です。
rm はファイルを削除します。ここで引用した唯一の対象は新しい練習メモで、原本やディレクトリ全体ではありません。
rm 'notes/practice/new notes.txt'
./findnotes notes cat
その識別子が消え、参照の 2 件は残ります。原本を削除したり、結果を強制するためにパーサーを変えたりしないでください。パスを間違えたら No such file or directory を読み、find notes -type f で実在パスを列挙して正しいものを使います。読み取り専用原本を指定してしまったら変更せず、練習ファイルを使ってください。普通のパス誤りで環境をリセットする必要はありません。
自己チェックを再実行します。現在のファイルを読み、ほかの入力用に使い捨てテストデータを作ります。そこでの編集、追加、削除は練習データを一切変更しません。不正入力を隔離して試すと、PASS 行の隣に想定どおりのエラーが出る場合があります。成功した実行は CLI CHECKS PASSED で終わります。
bash /opt/labex-note-search/check.sh index
チェックボタンも成功するはずです。繰り返してもコードを書き換えず、実行ファイルを置換せず、練習メモをリセットしません。ソース編集後に失敗したら、実際の findnotes を再ビルドして再試行します。関数の一時テストだけでは、実行ファイルが最新であるとは証明できません。
まとめ
完全な文書識別子の集合を値に持つ転置インデックスを作りました。単語の反復で文書は重複せず、同じベース名も別々に扱われ、実際の行番号から原文に戻れます。許可された練習の編集、追加、削除は、再実行時の自動的な索引再構築に反映されます。次は同じ文書に複数の単語を要求する積集合を実装します。
