検索エンジンに品詞情報を付加する：具体的な検索アルゴリズムの解説(stanza)(PHP)
英語・語句選択問題検索が品詞による検索に対応しました。この投稿では，自作の検索エンジンで品詞を用いた検索を実現する方法と，そのアルゴリズムについて紹介します。
品詞情報の取得
品詞を用いた検索を実現するためには，検索対象となるデータから品詞情報を抽出する必要があります。品詞情報を抽出する方法は有料・無料のものを含めていくつか選択肢がありますが，ここではオープンソースであるstanzaを使用します。
stanzaを用いた品詞情報の抽出方法については，NLP(自然言語処理) Stanzaによる構文解析の結果を取得するを参照して下さい。言語はpythonを使用します。データベースが大きくなると，かなりの計算時間を要します。
stanzaを用いると，以下のような品詞情報が抽出できます。
Look! There's a dog in the hall.
"VB", ".", "EX", "VBZ", "DT", "NN", "IN", "DT", "NN", "."stanzaが抽出する品詞情報にはUPOSとXPOSの二つがありますが，今回はより細かい品詞情報を利用するためにXPOSを採用しています。例えば，VBは動詞原形を表します。品詞記号の意味については上記のリンクを参考して下さい。
検索エンジンの特性
今回作成している全文検索エンジンは少し特殊なものです。４つの選択肢を持つ英文法の語句選択問題からそれぞれの選択肢を空欄に当てはめた英文を作成し，入力された検索語との近似度をスコア化しています。例えば
Look! There’s a dog in the hall. Someone must have left the door ( ).
1. be opened 2. open 3. opening 4. to open
という問題文があった場合，これをもとに４つの英文を作成します。
Look! There’s a dog in the hall. Someone must have left the door be opened.
Look! There’s a dog in the hall. Someone must have left the door open.
Look! There’s a dog in the hall. Someone must have left the door opening.
Look! There’s a dog in the hall. Someone must have left the door to open.
これらのうち３つは誤った英文ですが，すべて検索対象とします。
そして，stanzaを用いて４つの英文の品詞情報を抽出し，検索語と近いものほどスコアが高くなるように設定します。最もスコアの高いものがその問題文のスコアとして設定され，データベースに登録された問題文の中でスコアの高いものから順に検索結果として表示します。
また，検索するデータはレンマ化したものを用います。レンマとは辞書における単語の見出し語のことで，動詞で言えば原形のことです。たとえば，takes，took，taking，takenはデータベース上ではすべてtakeとして登録されています。こうすることで，検索の際に単語の活用形を考える必要がなくなる一方で，たとえばtakeではなくtakenを検索したいという場合に，現状の仕様では検索できないことになります。この点は，考慮の余地があるのかもしれません。
jsonファイルの読み込み
$json = file_get_contents('compress.zlib://data/base_contents.json.gz');
$json = mb_convert_encoding($json, 'UTF8', 'ASCII,JIS,UTF-8,EUC-JP,SJIS-WIN');
$text = json_decode($json,true);
$json = file_get_contents('compress.zlib://data/chars.json.gz');
$json = mb_convert_encoding($json, 'UTF8', 'ASCII,JIS,UTF-8,EUC-JP,SJIS-WIN');
$chars = json_decode($json,true);
$json = file_get_contents('compress.zlib://data/lemma.json.gz');
$json = mb_convert_encoding($json, 'UTF8', 'ASCII,JIS,UTF-8,EUC-JP,SJIS-WIN');
$lemmas = json_decode($json,true);
$json = file_get_contents('compress.zlib://data/xpos.json.gz');
$json = mb_convert_encoding($json, 'UTF8', 'ASCII,JIS,UTF-8,EUC-JP,SJIS-WIN');
$xposes = json_decode($json,true);具体的なコードの説明に移ります。stanzaを用いて解析したデータを順次読み込んでいきます。データベースが大きくなってきたので，gz形式で圧縮したものをサーバーにアップロードして，読み込み時間を削減しています（体感速度の差はほとんどありませんが）。ファイル名の先頭にcompress.zlib://を付け加えると，圧縮ファイルを自動的に解凍して取り出すことができます。また，jsonファイルはエンコードをしないと文字化けを起こすのでmb_convert_encodingでエンコードしておきます。
もともとのデータは$textに格納します。
$text[0] =
"Look! There's a dog in the hall. Someone must have left the door #.",
"be opened",
"open",
"opening",
"to open",
"センター試験"stanzaを用いて抽出した情報をレンマ化された単語$lemmas，品詞情報$xposesに格納します。
$lemmas[0][0] =
"look", "!", "there", "be", "a", "dog", "in", "the", "hall", ".", "someone", "must", "have", "leave", "the", "door", "be", "open", "."
$lemmas[0][1] =
"look", "!", "there", "be", "a", "dog", "in", "the", "hall", ".", "someone", "must", "have", "leave", "the", "door", "open", "."
$lemmas[0][2] =
"look", "!", "there", "be", "a", "dog", "in", "the", "hall", ".", "someone", "must", "have", "leave", "the", "door", "opening", "."
$lemmas[0][3] =
"look", "!", "there", "be", "a", "dog", "in", "the", "hall", ".", "someone", "must", "have", "leave", "the", "door", "to", "open", "."$xposes[0][0] =
"VB", ".", "EX", "VBZ", "DT", "NN", "IN", "DT", "NN", ".", "NN", "MD", "VB", "VBN", "DT", "NN", "VB", "VBN", "."
$xposes[0][1] =
"VB", ".", "EX", "VBZ", "DT", "NN", "IN", "DT", "NN", ".", "NN", "MD", "VB", "VBN", "DT", "NN", "JJ", "."
$xposes[0][2] =
"VB", ".", "EX", "VBZ", "DT", "NN", "IN", "DT", "NN", ".", "NN", "MD", "VB", "VBN", "DT", "NN", "NN", "."
$xposes[0][3] =
"VB", ".", "EX", "VBZ", "DT", "NN", "IN", "DT", "NN", ".", "NN", "MD", "VB", "VBN", "DT", "NN", "TO", "VB", "."ここで，レンマ化された単語と品詞情報が一致しないことに注意してください。品詞情報はレンマ化される前の情報をもとに抽出されます。
$query = htmlspecialchars(@$_GET['search'], ENT_QUOTES, 'UTF-8');
$ln = @$_GET['label'];
$q_chars = explode(" ",$query);
$q_len = count($q_chars);入力された検索文字列を$queryに格納します。入力フォームにname="search"を設定して，文字列を@$_GET['search']で取り出します。次にexplode()で検索文字列を単語ごとに分割し，配列$q_charsに格納します。さらに，入力された単語の数をcount()で数え，$q_lenに格納します。
問題文を順次検索する
検索部分のパーツは検索ボックス，検索ボタン，２つのトグルボタンによって構成されています。
ここでは，「問題文と選択肢」の検索を，関数Gsearch_text_option()として定義します。
function Gsearch_text_option() {
global $text, $chars, $lemmas, $xposes, $ln, $ln1, $ln2, $ln3, $ln4;
global $query, $q_chars, $q_len;関数の外で定義された変数を関数の中で使うために，globalで変数の引継ぎを宣言する必要があります。
for ($id = 0; $id < count($text); $id++) {
for ($option = 0; $option <= 3; $option++) {
$score_by_option = array(0,0,0,0);
$chars_len = count($lemmas[$id][$option]);
$seq = -1;データベースの問題文の番号を$idとし，それぞれが持つ４つの英文を$optionで表します。これらをfor文で順次検索していきます。
４つの英文について，それぞれ計算したスコアを$score_by_optionに格納します。あとで，４つのスコアの最大値をその問題文のスコアとします。
$chars_lenにはこれからスコアを判定する英文の単語数をcountで数え，格納します。$seqは検索する単語に一致するものがみつかった場合，それが文の先頭から何番目に存在したかを格納します。初期値は-1としておきます。
検索アルゴリズム
検索アルゴリズムの概要を説明をします。たとえば，
Look! There’s a dog in the hall. Someone must have left the door open.
という英文に対してhave [VBN]を検索する場合を考えます。[VBN]は過去分詞を表す記号です。
実際の検索はレンマ化されたデータに対して行います。leftが原形のleaveになっていることを確認してください。
$lemmas[0][1] =
"look", "!", "there", "be", "a", "dog", "in", "the", "hall", ".", "someone", "must", "have", "leave", "the", "door", "open", "."はじめに，データからhaveを検索します。配列の先頭から要素がhaveに一致するかどうかを判定していきます。配列の先頭は0番目から始まることに注意してください。
ここでは，英文の12番目がhaveに一致します。配列としては$lemmas[0][1][12]のデータということになります。単語がみつかったのでスコアを100ポイント加算し，$seq=12とします。実際には，ここでスコアから12を引き，88ポイントを加算します。これは，検索する単語が文の先頭に近いほど高いスコアとするためです。
そして，残りの単語の判定はスキップし，次の検索語である[VBN]の判定に進みます。
次に[VBN]を検索します。検索語が[ ]で囲まれている場合は，品詞情報のデータを用いて判定していきます。
$xposes[0][1] =
"VB", ".", "EX", "VBZ", "DT", "NN", "IN", "DT", "NN", ".", "NN", "MD", "VB", "VBN", "DT", "NN", "JJ", "."今度は先頭から判定せず，$seq=12の情報を用いて，それの次にあたる13番目から判定していきます。このようにしないと，検索対象の英文にhave leftが含まれる場合と，left haveが含まれる場合で同じスコアになってしまいます。そこで，検索語の語順を考慮しています。
ここでは，13番目にVBNが存在しています。品詞がみつかったのでスコアを100ポイント加算します。
さらに，haveと[VBN]との距離を考慮します。haveは12番目，[VBN]は13番目なので，その距離を13-12=1とし，それを5倍した5ポイントを引きます。結果として，95ポイントが加算されることになります。
このようにしているのは，英文は副詞などの単語が挿入されることがあるためです。
たとえば，have finishedを検索する場合，対象となる英文にはhave finishedやhave already finished，have not finishedなど，様々な形が存在します。
このアルゴリズムではこれらを検索語に一致するものとして扱い，have finishedがhave already finishedよりも高いスコアになるようにしています。
スコアの加算と減算はあくまで恣意的なものです。実際に検索エンジンを運用しながら，最適な結果が得られるように値を調整する必要があります。
アルゴリズムを実際のコードで見ていきます。
for ($i = 0; $i < $q_len; $i++) {
$q_char = $q_chars[$i];検索する単語の数だけfor文で繰り返し処理します。have [VBN]で検索した場合，単語数が2個なので，2回繰り返し処理します。$q_charは検索する単語を格納します。1回目のループではhave，2回目のループでは[VBN]が格納されます。
for ($j = 0; $j < $chars_len; $j++) {検索対象の英文について，先頭から順番に繰り返し処理します。$jは先頭から何番目の単語かを表すことになります。
if ($seq == -1 || $j > $seq) {はじめにhaveについて判定するとき，$seqは初期値が-1だったので，if以下の処理を行います。また，[VBN]を判定するとき，$seq=12となっているので，$jが0から12まではif以下の処理を行いません。こうして，検索語の語順を考慮した判定処理のスキップを行います。
if(preg_match('/\[.*\]/u',$q_char)) {
$char = $xposes[$id][$option][$j];
if(strcmp($q_char, '['.$char.']') == 0) {
$score_by_option[$option] += 100 - $j;
break;
}先に品詞情報による判定を行います。preg_match()は正規表現による文字列の判定を行います。ここでは，単語が[ ]で囲まれている場合に，それを品詞として判定します。
次に，品詞情報が格納された配列$xposesから品詞記号を抽出し，$charに格納します。英文の先頭から判定を行い，検索語と一致した場合，$score_by_option[$option]にスコアを加算します。strcmp()２つの文字列を比較し，一致した場合に０を返します。ここでは，１つの問題文につき４つの英文が存在しているので，それぞれの英文についてのスコアを配列に格納します。あとで，この配列の最大値をその問題文のスコアとします。
また，一致する品詞が見つかった時点でbreakによってループを抜け出し，残りの単語についての判定をスキップします。
} else {
$char = $lemmas[$id][$option][$j];
if (strcmp($q_char, $char) == 0 && $i == 0) {
$score_by_option[$option] += 100 - $j;
$seq = $j;
break;
}
if (strcmp($q_char, $char) == 0 && $i != 0) {
$score_by_option[$option] += 100 - ($j - $seq)*5;
$seq = $j;
break;
}
}次に，通常の単語について判定します。今度はレンマ化された単語情報が格納された配列$lemmasから単語を取り出し，$charに格納します。
そして，strcmp()で単語の一致を判定し，スコアを加算します。検索語の先頭の単語($i=0)と２番目以降($i!=0)でスコアの加算方法が異なるので，処理を分けます。
また，上と同様に一致する単語が見つかった時点で，英文の残りの単語についての判定をbreakでスキップします。
if ($score_by_option[$option] == 0) {
break;
}一つ目の検索語が英文の中に存在しなかった場合，スコアは0になるので，残りの判定をスキップして，次の英文に進みます。
$scores[$id] = max($score_by_option);
４つの英文のスコアの最大値をその英文のスコアとし，配列$scoresに格納します。
arsort($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>
<?php
//jsonファイルの読み込み
$json = file_get_contents('compress.zlib://data/base_contents.json.gz');
$json = mb_convert_encoding($json, 'UTF8', 'ASCII,JIS,UTF-8,EUC-JP,SJIS-WIN');
$text = json_decode($json,true);
$json = file_get_contents('compress.zlib://data/chars.json.gz');
$json = mb_convert_encoding($json, 'UTF8', 'ASCII,JIS,UTF-8,EUC-JP,SJIS-WIN');
$chars = json_decode($json,true);
$json = file_get_contents('compress.zlib://data/lemma.json.gz');
$json = mb_convert_encoding($json, 'UTF8', 'ASCII,JIS,UTF-8,EUC-JP,SJIS-WIN');
$lemmas = json_decode($json,true);
$json = file_get_contents('compress.zlib://data/xpos.json.gz');
$json = mb_convert_encoding($json, 'UTF8', 'ASCII,JIS,UTF-8,EUC-JP,SJIS-WIN');
$xposes = json_decode($json,true);
$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","エ");
$query = htmlspecialchars(@$_GET['search'], ENT_QUOTES, 'UTF-8');
$ln = @$_GET['label'];
$q_chars = explode(" ",$query);
$q_len = count($q_chars);
//検索結果の表示
function Gsearch_text_option() {
global $text, $chars, $lemmas, $xposes, $ln, $ln1, $ln2, $ln3, $ln4;
global $query, $q_chars, $q_len;
for ($id = 0; $id < count($text); $id++) {
for ($option = 0; $option <= 3; $option++) {
$score_by_option = array(0,0,0,0);
$chars_len = count($lemmas[$id][$option]);
$seq = -1;
//検索文字列を単語ごとに判定
for ($i = 0; $i < $q_len; $i++) {
$q_char = $q_chars[$i];
//問題文の先頭から検索
for ($j = 0; $j < $chars_len; $j++) {
if ($seq == -1 || $j > $seq) {
//品詞オプションあり
if(preg_match('/\[.*\]/u',$q_char)) {
$char = $xposes[$id][$option][$j];
//検索する品詞がみつかった場合
if(strcmp($q_char, '['.$char.']') == 0) {
$score_by_option[$option] += 100 - $j;
break;
}
} else {
//通常の単語
$char = $lemmas[$id][$option][$j];
if (strcmp($q_char, $char) == 0 && $i == 0) {
$score_by_option[$option] += 100 - $j;
$seq = $j;
break;
}
if (strcmp($q_char, $char) == 0 && $i != 0) {
$score_by_option[$option] += 100 - ($j - $seq)*5;
$seq = $j;
$hit[$id] = $seq;
break;
}
}
}
}
if ($score_by_option[$option] == 0) {
break;
}
}
}
$scores[$id] = max($score_by_option);
}
arsort($scores); #検索結果の並べ替え
//検索結果の表示
$count = 0;
foreach($scores as $key => $value) {
echo "<p>";
#echo $scores[$key].': ';
echo str_ireplace("#","( )",$text[$key][0]);
echo " <span class='univ_name'>(".$text[$key][5].")</span>";
echo "</p>";
echo "<p style='text-indent:1.5em' class='mb-4'>";
echo $ln1[$ln]." ".$text[$key][1];
echo " ".$ln2[$ln]." ".$text[$key][2];
echo " ".$ln3[$ln]." ".$text[$key][3];
echo " ".$ln4[$ln]." ".$text[$key][4];
echo "</p>";
$count += 1;
if ($count == 30) {
break;
}
}
}
function Gsearch_option() {
global $text, $chars, $xposes, $ln, $ln1, $ln2, $ln3, $ln4;
global $query, $q_chars, $q_len;
$count = 0;
for ($id = 0; $id < count($text); $id++) {
$score_min = 100;
for($i=0;$i<=3;$i++){
$score = levenshtein(mb_strtolower($query), mb_strtolower(substr($text[$id][$i],0,15)));
if ($score < $score_min) {
$score_min = $score;
}
}
$scores[$id] = $score_min;
}
asort($scores);
$count = 0;
foreach($scores as $key => $value) {
echo "<p class='mb-4'>";
echo $ln1[$ln]." ".$text[$key][1];
echo " ".$ln2[$ln]." ".$text[$key][2];
echo " ".$ln3[$ln]." ".$text[$key][3];
echo " ".$ln4[$ln]." ".$text[$key][4];
echo "</p>";
$count += 1;
if ($count == 30) {
break;
}
}
}
?>
<div class="container">
<header class="mt-2">
<p>
<?php
echo "英語・語句選択問題検索<span class='badge badge-success ml-2 mr-2'>ベータ版</span>データベースの登録設問数：".count($text);
?>
</p>
</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>
<p>品詞オプション：[CC]等位接続詞 [IN]前置詞/従位接続詞 [JJ]形容詞 [JJR]形容詞比較級 [JJS]形容詞最上級 [MD]助動詞 [NN]名詞単数形 [NNS]名詞複数形 [NNP]固有名詞単数形 [NNPS]固有名詞複数形 [PRP]人称代名詞 [RB]副詞 [RBR]副詞比較級 [RBS]副詞最上級 [VBD]動詞過去形 [VBG]動名詞/現在分詞 [VBN]過去分詞 [VBP]動詞三人称単数以外 [VBZ]動詞三人称単数 [WDT]whatやwhichなど [WP]関係代名詞 [WRB]関係副詞</p>
<div id="result" class="mt-4">
<?php
if (@$_GET['search'] != null && @$_GET['display'] == 0) {
Gsearch_text_option(); #問題文と選択肢の検索
}
if (@$_GET['search'] != null && @$_GET['display'] == 1) {
Gsearch_option(); #選択肢のみ検索
}
?>
</div>
</article>
<footer class="text-right mb-5">2020 <a href="https://mmsankosho.com">mm参考書</a></footer>
</div>
</body>
</html>SNSでシェア