LANG SELRCT

コードを書く場所についてはこちら

2017年11月7日火曜日

シート内でキーワードに一致する値を探す(二分探索で日本語を探索してみる)


数値やアルファベットの二分探索と同じ方法では日本語の探索がうまくいかなかったため、今回は日本語を二分探索する方法を書いていこうと思います


方法としては
  • 日本語を数値に変換して
  • その数値を昇順でソートして
  • 二分探索を行う
というプロセスでやってみます


関連する記事



コード.gs
function binarysearch() {
  var keyword = "東京都";
  var keyword_code = parseInt(get_char_code(keyword));
  var ss = SpreadsheetApp.getActiveSpreadsheet();
  var sh = ss.getActiveSheet();
  var range = sh.getRange("A2:A");
  var values = range.getValues();
  for (var i = 0; i < values.length; i++) {
    var text = values[i][0];
    var code = parseInt(get_char_code(text));
    sh.getRange((i + 2), 2).setValue(code)
  }
  var sort_range = sh.getRange("A2:B");
  sort_range.sort([{
    column: 2,
    ascending: true
  }]);
  var code_range = sh.getRange("B2:B");
  var code_values = code_range.getDisplayValues();
  var head = 0;
  var tail = code_values.length - 1;
  var row = 0;
  while (head <= tail) {
    var middle = Math.floor((head + tail) / 2);
    row = middle + 2;
    if (parseInt(code_values[middle][0]) == keyword_code) {
      break;
    } else if (parseInt(code_values[middle][0]) < keyword_code) {
      Logger.log([row + "行目" + values[middle][0] + "より大きい"]);
      head = middle + 1;
    } else {
      Logger.log([row + "行目" + values[middle][0] + "より小さい"]);
      tail = middle - 1;
    }
  }
  Logger.log(keyword + "は " + (row) + "行目です")
}

function get_char_code(text) {
  var code_array = [];
  for (var i = 0; i < text.length; i++) {
    code_array.push(text[i].charCodeAt());
  }
  var keyword_code = code_array.toString().replace(/,/g, "");
  return keyword_code;
}
意訳.gs
この処理は以下を実行する
探したいテキストを指定して
それをget_char_codeで処理して数値に変換する
現在開いているスプレッドシートの
開いているシートの
A2:Aの範囲の
値をすべて取得して
値の数だけ以下の処理を繰り返す
textに値を入れて
それをget_char_codeで処理して数値に変換する
2つめの列(つまりB列)に入力する

A2:Bの範囲を取得し
以下設定でソートする
基準の列は2(つまり数値の入っているB列)
昇順にする

B2:Bの範囲を取得して
表示されている値をすべて取得する
探索範囲の先頭の初期値を0にして
探索範囲の末尾の初期値はA列の値の個数-1にする
rowの初期値は0にする
先頭の数値が末尾の数値以下である限り
対象範囲の中央の値を取得し
行数はその値に+2したもの(code_values[0][0]はB2の値なので行数には+2する必要がある)
もしその中央の値が探している値なら
処理から抜ける
もし中央の値が探している値よりも小さいなら
探している値は中央よりも大きい方にあるとログに出す
次に探す範囲の先頭は中央の値の下からにする
それ以外(中央の値が探している値よりも大きい)なら
探している値は中央よりも小さい方にあるとログに出す
次に探す範囲の末尾は中央の値のひとつ上にする


最終的に見つけた行数をログに出す


この処理は以下を実行する
code_arrayという入れ物を用意して
textの文字数だけ以下の処理を繰り返す
code_arrayにtextの一文字ずつを数値変換した値を追加していく

code_arrayを文字列に変換してカンマを削除した値をkeyword_codeに入れて
返す


試してみる


例としてこんなシートを用意して


上記コード.gsのbinarysearch()を実行すると
各都道府県名を数値変換したものがB列に入力されて
B列が昇順でソートされます

そしてこの中から「東京都」が何行目にあるのかを二分探索で見つけるプロセスと結果がログに出ます



今回使ったデータ


都道府県数値変換
北海道
青森県
岩手県
宮城県
秋田県
山形県
福島県
茨城県
栃木県
群馬県
埼玉県
千葉県
東京都
神奈川県
新潟県
富山県
石川県
福井県
山梨県
長野県
岐阜県
静岡県
愛知県
三重県
滋賀県
京都府
大阪府
兵庫県
奈良県
和歌山県
鳥取県
島根県
岡山県
広島県
山口県
徳島県
香川県
愛媛県
高知県
福岡県
佐賀県
長崎県
熊本県
大分県
宮崎県
鹿児島県
沖縄県