英語・語句選択問題検索サイトとその作り方ー検索アルゴリズムの改良
前回の記事で，英語・語句選択問題検索サイトとそのコードについて説明しましたが，検索の柔軟性をもう少し改善するために，検索アルゴリズムの改良を行いました。また，その他の部分についてもコードの改良を加えているので，それらも紹介します。
ディレクトリ内にある複数のファイルを読み込む
全文検索のためのデータベースが徐々に大きくなってきたので，複数のファイルに分けて管理することにしました。
$dir = './data/';
$files = scandir($dir);
$texts = array();
for ($i = 2; $i < count($files); $i++) {
$document = file($dir.$files[$i], FILE_IGNORE_NEW_LINES | FILE_SKIP_EMPTY_LINES);
$texts = array_merge($texts, $document);
}
scandir()は指定したディレクトリ内にあるファイルの一覧を配列として返し，配列$filesに格納します。実際にファイル名が格納されているのは配列の３番目からなので，for文による繰り返し処理を$i=2から開始します。
file()はテキストファイルの内容を１行ごとに配列として返します。それを配列$document()に格納します。
array_merge()は配列どうしを連結します。配列$textsにそれぞれのファイルのテキストを追加していき，ディレクトリ内のテキスト全文を一つの配列にまとめます。
そしてこの$textsに対して，全文検索を行います。
トグルボタンの設置
トグルボタンは同じようなコードの繰り返しになるので，繰り返し部分をfor文でまとめてみました。
$checked = array("","");
$content = array("問題文と選択肢","選択肢のみ");
if (@$_GET['display'] == null) {
$checked[0] = "checked";
} else {
$checked[@$_GET['display']] = "checked";
}
for ($i = 0; $i < count($checked); $i++) {
echo '<label class="btn btn-outline-info">';
echo '<input type="radio" name="display" value="'.$i.'" '.$checked[$i].'>'.$content[$i];
echo '</label>';
}
詳しい説明は省略しますが，ここでは選択されたボタンが持つvalueの値に応じて<input>タグの最後にcheckedを挿入することで，検索ボタンが押されたときにボタンの選択がリセットされないようにしています。
$checked = array("","","","","","","","");
$content = array("1.","1","①","A.","A","a.","a","ア");
if (@$_GET['label'] == null) {
$checked[0] = "checked";
} else {
$checked[@$_GET['label']] = "checked";
}
for ($i = 0; $i < count($checked); $i++) {
echo '<label class="btn btn-outline-info">';
echo '<input type="radio" name="label" value="'.$i.'" '.$checked[$i].'>'.$content[$i];
echo '</label>';
}
二つ目のトグルボタンも一つ目とほとんど同じコードです。
検索の実行
検索アルゴリズムの部分について変更点を説明していきます。
for ($id = 0; $id < count($text); $id++) {
$fixed_text[$id][0] = str_ireplace("#",$option1[$id],$text[$id]);
$fixed_text[$id][1] = str_ireplace("#",$option2[$id],$text[$id]);
$fixed_text[$id][2] = str_ireplace("#",$option3[$id],$text[$id]);
$fixed_text[$id][3] = str_ireplace("#",$option4[$id],$text[$id]);
$text[0] = "After a lot of problems she # to learn to drive a car."
$option1[0] = "gave up"
$option2[0] = "managed"
$option3[0] = "put off"
$option4[0] = "succeeded"
--->
$fixed_text[0] = "After a lot of problems she gave up to learn to drive a car."
$fixed_text[1] = "After a lot of problems she managed to learn to drive a car."
$fixed_text[2] = "After a lot of problems she put off to learn to drive a car."
$fixed_text[3] = "After a lot of problems she succeeded to learn to drive a car."
今回の全文検索エンジンは英文法問題の問題文と選択肢について検索をかけていくので，一般的な全文検索に対してやや特殊な処理が必要です。
まず，問題文の括弧の部分をそれぞれの選択肢に置換した文を作ります。選択肢は４つあるので４つの文ができます。こうして作られた文に対して，検索文字と類似しているかどうかを調べていきます。これをデータベースにある問題文の数だけ繰り返し処理します。
今回考案した検索アルゴリズムはこのようなものです。まず，検索語が複数の単語で構成されているとして，検索語の１番目と，文の1番目，2番目，・・・を順番にlevenshtein()で比較し，単語どうしの一致度を調べます。そして，文の中で最も単語が似ているものを次の検索のスタート地点として，検索語の２番目と，文の単語を順番に比較していきます。
例えば，検索語がmanage toで，検索対象文字列がAfter a lot of problems she managed to learn to drive a car.だとします。この場合，まずmanageとafter，a，lot，・・・を順番に比べていきます。このとき，７番目のmanagedが最も類似していると判断されるはずです。次に，７番目をスタート地点として，toとmanaged，to，learn，・・・を順番に比べていきます。今度は，８番目のtoが最も類似していると判断されます。
levenshtein()は文字列が類似しているほど小さな値を返すので，類似度の合計は小さな値になります。反対に，類似度の小さな単語がみつからない場合は，合計は大きな値になるでしょう。
こうして，それぞれの文の類似度の合計を小さいものから順に並べ替えかえることで検索結果を表示します。
検索対象文字列のスタート地点を移動させているのは，検索語の順番を考慮しているためです。このような処理をしないと，理屈から言えばmanage toとto manageの検索結果が同じになってしまうはずです。
また，このアルゴリズムは検索の柔軟性を向上させます。例えば，検索語をhave the purse stolenとしたとき，I had my purse stolen.やMy mother had her purse she bought yesterday stolen.も類似した文として判定します。ただし，このように検索結果の柔軟性を上げると，本来検索したい文とかけ離れたものも類似していると判定する確率が高くなります。この辺りは実際に検索エンジンを運用しながら改善策を考える必要がありそうです。
for ($option = 0; $option <= 3; $option++) {
$chars = explode(" ", mb_strtolower($fixed_text[$option]));
$chars_len = count($chars);
$seq_index = 0;
for ($i = 0; $i < $q_len; $i++){
$score_min = 100;
for ($j = 0; $j < $chars_len; $j++) {
if ($j >= $seq_index) {
$score = levenshtein($q_chars[$i],$chars[$j]);
if ($score < $score_min) {
$score_min = $score;
$k = $j;
}
}
}
$seq_index = $k;
if ($i == 0) {
$scores[$id] = $score_min;
} else {
$scores[$id] += $score_min;
}
}
}実際のコードです。for文を用いて，上で作成した４つの文それぞれについて処理を行っていきます。
mb_strtolower()は文字列を小文字に変換します。こうして，大文字と小文字の違いを無視して比較します。
explode()は文字列を分割して配列に格納します。ここでは単語の間の空白で文字列を分割し，配列$charsに格納します。
for ($i = 0; $i < $q_len; $i++){
検索語の単語数だけ繰り返し処理します。例えば，検索語がin order toなら単語数は３個なので，$iは0から2まで変化します。
$score_min = 100;
$score_minは類似度の最小値を格納します。混乱しやすいですが，levenshtein()は類似度が高いほど小さな値を返すことを思い出してください。初期値として100を設定します。実際のところ，levenshtein()で一つの単語どうしを比較した場合，返り値が10を超えることはほとんどないでしょう。
for ($j = 0; $j < $chars_len; $j++) {
if ($j >= $seq_index) {
$score = levenshtein($q_chars[$i],$chars[$j]);
}
if ($score < $score_min) {
$score_min = $score;
$k = $j;
}
}
$seq_index = $k;
$chars_lenは検索対象文字列の単語数を表します。はじめ，$seq_indexは0なので，検索対象文字列の先頭から単語を比較していきます。そして，得られた$scoreが最小値である場合に$score_minの値を書き換えます。また，このときの単語が先頭から何番目にあるかを$kに保存します。
$kの値は繰り返し処理の中で常に変化していくので，その最終的な結果を$seq_indexに格納します。この処理は，for文のループの範囲を固定するために必要なものです。
if ($i == 0) {
$scores[$id] = $score_min;
} else {
$scores[$id] += $score_min;
}
比較の最小値の合計を求めます。$i=0，つまり１番目の単語について処理しているときには$scoresには値が存在しないので，最小値をそのまま代入し，２番目以降の場合には，最小値の値を加算するようにしています。
コード全体を示します。
<html lang="ja">
<head>
<meta charset="utf-8">
<title>英語・語句選択問題検索</title>
<!--boostrap-->
<script src="https://code.jquery.com/jquery-3.5.1.slim.min.js" integrity="sha384-DfXdz2htPH0lsSSs5nCTpuj/zy4C+OGpamoFVy38MVBnE+IbbVYUew+OrCXaRkfj" crossorigin="anonymous"></script>
<script src="https://cdn.jsdelivr.net/npm/popper.js@1.16.0/dist/umd/popper.min.js" integrity="sha384-Q6E9RHvbIyZFJoft+2mJbHaEWldlvI9IOYy5n3zV9zzTtmI3UksdQRVvoxMfooAo" crossorigin="anonymous"></script>
<script src="https://stackpath.bootstrapcdn.com/bootstrap/4.5.0/js/bootstrap.min.js" integrity="sha384-OgVRvuATP1z7JjHLkuOU7Xw704+h835Lr+6QL9UvYjZE3Ipu6Tp75j7Bh/kR0JKI" crossorigin="anonymous"></script>
<link rel="stylesheet" href="https://stackpath.bootstrapcdn.com/bootstrap/4.5.0/css/bootstrap.min.css" integrity="sha384-9aIt2nRpC12Uk9gS9baDl411NQApFmC26EwAOH8WgZl5MYYxFfc+NcPb1dKGj7Sk" crossorigin="anonymous">
<link rel="stylesheet" href="gsearch.css" type="text/css">
<!--[if lt IE 9]>
<script src="http://html5shiv.googlecode.com/svn/trunk/html5.js"></script>
<script src="http://css3-mediaqueries-js.googlecode.com/svn/trunk/css3-mediaqueries.js"></script>
<![endif]-->
</head>
<body>
<div class="container">
<?php
//全文の読み込み
$dir = './data/';
$files = scandir($dir);
$texts = array();
//ディレクトリのテキストを一つずつ抽出する
for ($i = 2; $i < count($files); $i++) {
$document = file($dir.$files[$i], FILE_IGNORE_NEW_LINES | FILE_SKIP_EMPTY_LINES);
$texts = array_merge($texts, $document);
}
?>
<header class="mt-2">
<?php
echo "英語・語句選択問題検索（試用版）データベースの登録設問数：".count($texts)/6;
?>
</header>
<article>
<form method="get">
<div class="form-row align-items-center">
<div>
<?php
//検索ボックス
echo '<input type="text" id="search_form" class="form-control mt-2 mb-2" name="search" size="33" maxlength="50"';
echo 'value="'.htmlspecialchars(@$_GET['search'], ENT_QUOTES, 'UTF-8').'" autofocus>';
?>
</div>
<div class="col-auto">
<input type="submit" class="btn btn-outline-info" value="検索">
</div>
<div class="btn-group btn-group-toggle ml-2" data-toggle="buttons">
<?php
//一つ目のトグルボタン
$checked = array("","");
$content = array("問題文と選択肢","選択肢のみ");
if (@$_GET['display'] == null) {
$checked[0] = "checked";
} else {
$checked[@$_GET['display']] = "checked";
}
for ($i = 0; $i < count($checked); $i++) {
echo '<label class="btn btn-outline-info">';
echo '<input type="radio" name="display" value="'.$i.'" '.$checked[$i].'>'.$content[$i];
echo '</label>';
}
?>
</div>
<div class="btn-group btn-group-toggle ml-2" data-toggle="buttons">
<?php
//二つ目のトグルボタン
$checked = array("","","","","","","","");
$content = array("1.","1","①","A.","A","a.","a","ア");
if (@$_GET['label'] == null) {
$checked[0] = "checked";
} else {
$checked[@$_GET['label']] = "checked";
}
for ($i = 0; $i < count($checked); $i++) {
echo '<label class="btn btn-outline-info">';
echo '<input type="radio" name="label" value="'.$i.'" '.$checked[$i].'>'.$content[$i];
echo '</label>';
}
?>
</div>
</div>
</form>
<div id="result" class="mt-4">
<?php
//検索結果の表示
if (@$_GET['search'] != null) {
$query = htmlspecialchars(@$_GET['search'], ENT_QUOTES, 'UTF-8');
$count = 0;
//txtの各行を配列に格納する
for ($i = 0; $i < count($texts); $i++) {
if ($i % 6 == 0) {
$text[$count] = $texts[$i];
}
if ($i % 6 == 1) {
$option1[$count] = $texts[$i];
}
if ($i % 6 == 2) {
$option2[$count] = $texts[$i];
}
if ($i % 6 == 3) {
$option3[$count] = $texts[$i];
}
if ($i % 6 == 4) {
$option4[$count] = $texts[$i];
}
if ($i % 6 == 5) {
$univ_name[$count] = $texts[$i];
$count += 1;
}
}
$ln1 = array("1.","1","①","A.","A","a.","a","ア");
$ln2 = array("2.","2","②","B.","B","b.","b","イ");
$ln3 = array("3.","3","③","C.","C","c.","c","ウ");
$ln4 = array("4.","4","④","D.","D","d.","d","エ");
$ln = @$_GET['label'];
if (@$_GET['display'] == 0) {
$q_chars = explode(" ",mb_strtolower($query));
$q_len = count($q_chars);
//文字列の一致度を計測する
for ($id = 0; $id < count($text); $id++) {
$fixed_text[0] = str_ireplace("#",$option1[$id],$text[$id]);
$fixed_text[1] = str_ireplace("#",$option2[$id],$text[$id]);
$fixed_text[2] = str_ireplace("#",$option3[$id],$text[$id]);
$fixed_text[3] = str_ireplace("#",$option4[$id],$text[$id]);
for ($option = 0; $option <= 3; $option++) {
$chars = explode(" ",mb_strtolower($fixed_text[$option]));
$chars_len = count($chars);
$seq_index = 0;
for ($i = 0; $i < $q_len; $i++){
$score_min = 100;
for ($j = 0; $j < $chars_len; $j++) {
if ($j >= $seq_index) {
$score = levenshtein($q_chars[$i],$chars[$j]);
if ($score < $score_min) {
$score_min = $score;
$k = $j;
}
}
}
$seq_index = $k;
if ($i == 0) {
$scores[$id] = $score_min;
} else {
$scores[$id] += $score_min;
}
}
}
}
asort($scores);
$count = 0;
foreach($scores as $key => $value) {
echo "<p>";
echo str_ireplace("#","( )",$text[$key]);
echo " <span class='univ_name'>(".$univ_name[$key].")</span>";
echo "</p>";
echo "<p style='text-indent:1.5em'>";
echo $ln1[$ln]." ".$option1[$key];
echo " ".$ln2[$ln]." ".$option2[$key];
echo " ".$ln3[$ln]." ".$option3[$key];
echo " ".$ln4[$ln]." ".$option4[$key];
echo "</p>";
$count += 1;
if ($count == 30) {
break;
}
}
}
if (@$_GET['display'] == 1) {
for ($id = 0; $id < 10; $id++) {
$score = levenshtein(mb_strtolower($query), mb_strtolower($option1[$id]));
$score_min = $score;
$score = levenshtein(mb_strtolower($query), mb_strtolower($option2[$id]));
if ($score < $score_min) {
$score_min = $score;
}
$score = levenshtein(mb_strtolower($query), mb_strtolower($option3[$id]));
if ($score < $score_min) {
$score_min = $score;
}
$score = levenshtein(mb_strtolower($query), mb_strtolower($option4[$id]));
if ($score < $score_min) {
$score_min = $score;
}
$scores[$id] = $score_min;
}
asort($scores);
foreach($scores as $key => $value) {
echo "<p>";
echo $ln1[$ln]." ".$option1[$key];
echo " ".$ln2[$ln]." ".$option2[$key];
echo " ".$ln3[$ln]." ".$option3[$key];
echo " ".$ln4[$ln]." ".$option4[$key];
echo "</p>";
}
}
}
?>
</div>
</article>
</div>
</body>
</html>SNSでシェア