はじめに
2 つの単語を覚えていれば、両方を含むメモに検索を絞れるはずです。単語は別々の行にあってもよく、同名の 2 つのメモも別文書でなければなりません。
この独立したラボは、正しい単語と文書の索引を提供します。クエリの積集合を実装し、本物の CLI 実行ファイルを再ビルドし、正常な空結果と不正入力を区別し、練習メモの変更後に検索します。前のラボの map、set、ASCII トークン、ターミナルとファイル操作を前提とします。55 分は作成者による見積もりです。
すべての検索語を含む文書だけを残す
このステップでは文書単位の AND を実装します。別々の行であっても、すべての検索語を含むメモだけが一致します。このラボは独立して始まり、正しい索引が準備済みで、前の環境には依存しません。WebIDE 内ではなく Terminal タブを使います。ファイルを変えず UTF-8 シェルを開きます。cd はこのシェルのディレクトリを変えるため、別の接続ではもう一度実行します。
cd /home/labex/project/note-search
完成済みのサンプルにディレクトリとクエリを渡します。単一引用符は 2 つの単語を 1 つのシェル引数に保ちます。プログラムはメモと同じ ASCII 規則でこの引数を解析します。
./sample notes 'cat blue'
practice/旅行 notes.txt と reference/archive/notes.txt が一致します。アーカイブの文書グループには次が含まれます。
File: reference/archive/notes.txt
1: CAT, cat!
2: Blue ledger — 東京
3: cat blue together
検索語を少なくとも1つ含む各行が、1 から始まる実際の行番号付きで 1 回ずつ表示されます。AND の判定は 1 行ではなく文書全体に対して行います。cat が 1 行目だけ、blue が 2 行目だけにあるメモも一致しなければなりません。同じ行での繰り返しや複数の検索語は、その行を重複させません。抜粋でも元の Unicode バイトが保たれます。
cat はファイルを表示します。インターフェースと準備済みの索引実装を読みます。
cat search.hpp
cat provided.inc
Index は単語から完全な相対文書識別子の集合への map です。単語の文書集合はポスティング集合とも呼ばれます。この単元の provided.inc は正しい buildIndex を提供します。engine.cpp には未完成の findAll があります。
cat engine.cpp
search.hpp、provided.inc、support.cpp、main.cpp、sample、および notes/reference/ 以下の全パスと内容を保ちます。編集は engine.cpp に行い、補助関数や同等のアルゴリズムを使えます。変更可能なデータは notes/practice/ だけで、初期のファイル構成を保つ必要はありません。準備済みの読み込み処理は通常の UTF-8 LF .txt ファイルを再帰的に読みます。空白や Unicode を含むパスに対応しますが、パス内のタブや改行、シンボリックリンク、NUL バイト、任意のバイナリは対象外です。読み取り失敗時はエラーになり、検索の部分結果は出ません。
準備済みの words() は ASCII 英字が連続する最大の範囲を取り出し、A-Z を a-z に変換します。数字、アンダースコア、句読点、空白、各非 ASCII バイトがトークンを区切ります。cat は catalog ではなく、CAT-blue_42 は cat と blue、猫cat狗 は cat、café は cafe でなく caf です。多言語の単語分割を行うわけではありません。findAll が受け取るのは、このパーサーで正規化済みの小文字 ASCII 検索語で、重複することもあります。語のリストが空なら、安全に空 vector を返す必要があります。一方 CLI は ASCII 単語のない生のクエリをステータス 2 で拒否し、stdout に結果を出しません。未知語や一致しない有効なクエリは通常の 0 と No matching documents. になります。
bash で自己チェックを実行し、query で完全なクエリ動作を選びます。開始コードは意図的に失敗し、通常は FAIL all documents, not only the first になります。ここでの非ゼロ状態は未完了を意味します。
bash /opt/labex-note-search/check.sh query
AND クエリでは、最初の語のポスティング集合をコピーします。次に残りの語の集合を 1 つずつ確認し、そのうち 1 つにでも候補識別子がなければ削除します。これが積集合です。未知の検索語があれば、すべての語を含む文書はありません。すべての集合を単に追加して合わせないでください。それは OR になり、要求語の 1 つしか含まないメモまで受け入れます。
terms.front() で先頭要素を使う前に terms.empty() を確認します。index.find(word) はキーを挿入せず検索し、index.end() はそのキーがないことを表します。存在しない項目を参照しないでください。見つかった項目では first->second または posting->second が -> を使ってイテレーター経由で項目にアクセスします。second はその値、つまり識別子の集合です。それを found にコピーし、クエリが索引を変えないようにします。
ループは集合内の位置であるイテレーターを使います。found.begin() は最初の位置、found.end() は最後の要素の次です。*it は現在の識別子です。ほかのポスティング集合にその識別子がなければ .count(*it) は 0 です。削除で古い位置が無効になるので、erase(it) が次の有効なイテレーターを返します。それ以外は ++it で通常どおり進めます。削除後に二重に進めないでください。
次の実装で engine.cpp を置き換えます。前と同じくヒアドキュメントでファイル全体を書き、> で置換し、引用した区切り 'CPP' でシェル展開を防ぎます。最後の CPP は単独の行にします。include はインターフェースと準備済みの正しい索引を維持します。
cat > engine.cpp <<'CPP'
#include "search.hpp"
#include "provided.inc"
std::vector<std::string> findAll(const Index& index,
const std::vector<std::string>& terms) {
if (terms.empty()) return {};
auto first = index.find(terms.front());
if (first == index.end()) return {};
std::set<std::string> found = first->second;
for (const auto& term : terms) {
auto posting = index.find(term);
if (posting == index.end()) return {};
for (auto it = found.begin(); it != found.end();) {
if (posting->second.count(*it) == 0) it = found.erase(it);
else ++it;
}
}
return std::vector<std::string>(found.begin(), found.end());
}
CPP
最後のコンストラクターは集合の残りの範囲を vector にコピーします。set の識別子は一意なので、各文書は 1 回だけ返ります。最初の語をループ内で再確認しても、集合と自分自身との積集合は変わらないため問題ありません。検索語の反復も同じ理由で無害です。積集合が空なら、そのまま空 vector を返します。パスの降順を含む別の再現可能なグループ順も許可されますが、各グループ内の行番号は昇順のままです。
現在のソースをコンパイルします。g++ が 3 つの .cpp をコンパイルし、-std=c++17 は C++17、-Wall -Wextra は警告、-o は実行ファイル名を指定します。include したファイルは engine.cpp 経由で自動的にコンパイルされます。
g++ -std=c++17 -Wall -Wextra engine.cpp support.cpp main.cpp -o findnotes
成功時は通常何も表示されません。失敗したら最初のファイルと行の診断を読み、engine.cpp を修正するか置換し直して再ビルドします。コンパイル失敗で古いバイナリが残る場合があります。チェックはソース関数と実際の既存 findnotes の両方を試し、代わりに再構築はしません。実行ファイルがない、または古い状態では完成した成果物ではありません。
./findnotes notes 'cat blue'
文書グループ全体と行の証拠をサンプルと比較します。準備済みの表示処理は返された識別子で実際の原文行を選びます。原本を書き換えたり固定の成功文を表示したりしても、検索の実装にはなりません。
空の結果と不正なクエリを区別する
このステップでは、繰り返す単語、トークンの境界、エラー、現在のファイルからの再構築を試します。Terminal のプロジェクトディレクトリに留まります。完成した関数は const Index& 入力を変更せず、同じ語で文書を重複させてはいけません。
./findnotes notes 'cat cat blue'
グループと行は cat blue と同じです。未知の語を加えます。
./findnotes notes 'cat absent'
No matching documents. になるはずです。cat だけを含む文書では足りません。有効でも答えのないクエリなので、終了状態は 0 です。コマンド直後のシェル変数 $? はその終了状態を持ち、二重引用符は 1 引数として展開します。printf で表示し、\n で改行します。
printf 'Exit status: %s\n' "$?"
Exit status: 0 と表示されます。大文字小文字の変換と区切りを試します。
./findnotes notes 'CAT-blue_42'
意味は cat blue と同じです。数字もアンダースコアもトークンの一部ではありません。完全な単語の検索は部分文字列の検索ではありません。
./findnotes notes catalog
一致するのは reference/catalog.txt と catalog を含む練習メモだけです。これは cat を意味しません。
空文字列は隣接する 2 つの単一引用符 '' で表します。渡されてはいるものの空のシェル引数です。次は意図した失敗で、stderr に Query needs at least one ASCII word を表示し、stdout に結果は出しません。
./findnotes notes ''
直後に終了状態を読みます。
printf 'Exit status: %s\n' "$?"
2 と表示されます。数字、区切り、非 ASCII 文字だけのクエリも同じ理由で不正です。
./findnotes notes '42_東京'
これも意図したステータス 2 の失敗です。Unicode の保存が壊れたわけではなく、対応する ASCII 単語がクエリにないだけです。原文やトークン分割を変えず、単語を含むクエリで復旧します。
ディレクトリのつづりを誤った場合は別のエラーです。次は存在しないディレクトリを意図的に指定します。
./findnotes missing-notes cat
Cannot read notes directory を表示し、部分結果を出さず 2 で終了します。実在パスを確認するなら find notes -type f を使い、正しいルートを指定して復旧します。
./findnotes notes cat
正常な結果に戻ります。いずれかの元ファイルが読めない場合にも、全体を読めなければエラーにする同じ規則が適用されます。一方、空でも読み取り可能なメモディレクトリは有効で、一致なしとなります。
準備済みの書き込み可能な練習コピーを変更します。単一引用符で空白と Unicode を含む名前を保ちます。printf はテキスト、\n は LF 改行を出力し、> がその練習ファイルを置換します。reference の原本は変更しません。
printf 'cat green\n東京 — preserved\n' > 'notes/practice/旅行 notes.txt'
./findnotes notes 'cat blue'
アーカイブの文書だけが残ります。練習メモが blue を含まなくなったためです。毎回現在のファイルを読み直して新しいメモリ内索引を作ります。保存済みキャッシュや追加の更新コマンドはありません。データの変更には再実行、C++ の変更には再コンパイルが必要です。
検索語が別の行にあるメモを追加します。
printf 'BLUE here\ncat elsewhere 東京\n' > 'notes/practice/new notes.txt'
./findnotes notes 'cat blue'
practice/new notes.txt が一致し、アーカイブの結果とともに 1、2 行目が出ます。行をまたいだ文書単位の AND の直接的な証拠です。rm は指定の練習ファイルだけを削除します。
rm 'notes/practice/new notes.txt'
./findnotes notes 'cat blue'
追加グループが消えます。パスを間違えたらファイルを列挙して正しいものを使い、VM はリセットしないでください。保護原本を指定してしまった場合は変更せず、練習ファイルを使います。正当な練習データの変更はすべて採点でも許可されます。
自己チェックを実行します。現在のプロジェクトを読み、ほかの入力は使い捨てデータで試します。バイナリの修復、現場のメモの編集、進捗のリセットはしません。不正入力テストの想定エラーが PASS の隣に出ることがあります。成功時は CLI CHECKS PASSED で終わります。
bash /opt/labex-note-search/check.sh query
ソースのテストが通っても実際の実行ファイルが失敗するなら、現在のソースから findnotes を再コンパイルして再試行します。繰り返すチェックは、エンジン、実行ファイル、準備済みファイル、原本、現在の練習内容を変えてはいけません。
まとめ
文書識別子の積集合として AND を実装し、別の行にある語も扱えました。語の反復は問題なく、未知語は正常な空結果、不正クエリや読み取れない入力は明示的な失敗になります。既存の実行ファイルは現在の練習データを読み、関連する原文行を各 1 回表示します。チャレンジではこのクエリ処理と索引作成を別のメモ集合で組み合わせます。
