0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

【Ruby のまずいコード】リストにある文字列を抽出

Last updated at Posted at 2021-12-16

お題

テキスト中から,リストで与えられた文字列をすべて抽出することを考えます。
たとえば

検索対象のテキスト(日本国憲法前文)
日本国民は、正当に選挙された国会における代表者を通じて行動し、われらとわれらの子孫のために、諸国民との協和による成果と、わが国全土にわたつて自由のもたらす恵沢を確保し、政府の行為によつて再び戦争の惨禍が起ることのないやうにすることを決意し、ここに主権が国民に存することを宣言し、この憲法を確定する。そもそも国政は、国民の厳粛な信託によるものであつて、その権威は国民に由来し、その権力は国民の代表者がこれを行使し、その福利は国民がこれを享受する。これは人類普遍の原理であり、この憲法は、かかる原理に基くものである。われらは、これに反する一切の憲法、法令及び詔勅を排除する。
日本国民は、恒久の平和を念願し、人間相互の関係を支配する崇高な理想を深く自覚するのであつて、平和を愛する諸国民の公正と信義に信頼して、われらの安全と生存を保持しようと決意した。われらは、平和を維持し、専制と隷従、圧迫と偏狭を地上から永遠に除去しようと努めてゐる国際社会において、名誉ある地位を占めたいと思ふ。われらは、全世界の国民が、ひとしく恐怖と欠乏から免かれ、平和のうちに生存する権利を有することを確認する。
われらは、いづれの国家も、自国のことのみに専念して他国を無視してはならないのであつて、政治道徳の法則は、普遍的なものであり、この法則に従ふことは、自国の主権を維持し、他国と対等関係に立たうとする各国の責務であると信ずる。
日本国民は、国家の名誉にかけ、全力をあげてこの崇高な理想と目的を達成することを誓ふ。

というテキストと,

["世界", "主権", "人間", "人類", "代表者", "信義", "信託", "信頼", ……(後略)

のような文字列リストが与えられたとき,

["国民", "選挙", "国会", "代表者", "国民", "自由", "政府", "戦争", ……(後略)

のように,リストにある文字列をテキスト中で前から順に重複ありで抜き出すものとします。
このようなメソッドを定義してください。

単語(あるいは形態素)を単位とする自然言語処理ではなく単純な文字列処理でよいとします。
たとえば,"人事" という文字列を「他社の人事は他人事だ」というテキストから拾う際,「他人事」の「人事」まで拾うのは,期待とは異なるかもしれませんが,それでよいことにします。

コード

コード 1

def retrieve(text, words)
  text.scan(/#{ words.join("|") }/)
end

コード 2

def retrieve(text, words)
  text.scan(/#{ words.map{ |s| Regexp.escape(s) }.join("|") }/)
end

{ } が入れ子になっているところで Qiita のコードハイライトが正しく行われず,見づらいですね)

講評

コード 1

コード 2 を見れば気づきますが,コード 1 では文字列のエスケープが行われません。
そのため,検索する文字列リストに . のようなメタ文字と解釈される文字が含まれている場合,適切な結果が得られないことになります。
場合によっては例外が発生します。

def retrieve(text, words)
  text.scan(/#{ words.join("|") }/)
end

p retrieve("telecomは遠距離通信", ["tel.com", "fax.com"])
# => ["telecom"]

p retrieve("RubyとかC++とか", ["Ruby", "C++"])
# => ["Ruby", "C"]

p retrieve("a+b-c", ["+", "-"])
# => RegexpError

コード 2

コード 2 は Regexp.escape を用いて,メタ文字(と解釈されてしまう文字)に \ を付けることで,上記の問題を回避しています。

Regexp.escape は以下のような動作のメソッドです:

puts Regexp.escape("3.14") # => 3\.14
puts Regexp.escape("A+B")  # => A\+B

ところで,コード 2 の動作には少し検討を要する点があります。
以下の例を見ましょう。

# コード 2 の再掲
def retrieve(text, words)
  text.scan(/#{ words.map{ |s| Regexp.escape(s) }.join("|") }/)
end

text = "JavaとJavaScriptは違います"

p retrieve(text, ["Java", "JavaScript"])
# => ["Java", "Java"]

p retrieve(text, ["JavaScript", "Java"])
# => ["Java", "JavaScript"]

検索したい文字列のリストを与えるとき,順序を変えると結果も変わりました。
「お題」に要件として書かなかったのですが1,こういう場合,リストの順序に関わらず後者のように拾って欲しいことが多いのではないでしょうか。

次節に移る前に,なぜ上記のような結果になったのかを見ておきましょう。
この現象を確認する単純化したコードを次に掲げます:

p "ABCD".scan(/B|BC/) # => ["B"]
p "ABCD".scan(/BC|B/) # => ["BC"]

1 行めで,なぜ "BC" ではなく "B" を拾ったのでしょう。
正規表現検索の「最長一致原則」について知っているなら,ますます不思議に思うかもしれません。検索対象に BC とあるのですから,BBC の長いほうを拾ってくれてもよさそうなものです。
実は,最長一致原則は + とか * とか ? のような量指定子について適用されるものであって,| のような選択(選言ともいう)については当てはまらないのです2
選択では,一つ見つかればそれ以降の選択肢は考慮されません3

改善

コード 2 の問題を解決するには,与えられた検索文字列リストをいったん長いもの順にソートしてやります。
Ruby では,文字列の配列を長いもの順に並べ替えるのがとても簡潔に記述できます。
Enumerable#sort_by を使えばこんなふうに:

languages = ["C", "C++", "FORTRAN", "Ruby"]

p languages.sort_by{ |language| -language.length } 
# => ["FORTRAN", "Ruby", "C+", "C"]

長さを符号反転したものを評価値として,その昇順に並べているわけですね。

この方法を使えば,お題はこんなふうに解けます:

def retrieve(text, words)
  words = words.sort_by{ -_1.length }
  text.scan(/#{ words.map{ Regexp.escape(_1) }.join("|") }/)
end

短く書くために Ruby 2.7 で導入された番号指定ブロックパラメーターを使いました。

これでまあ目的は達せられたわけですが,「配列の要素をエスケープ処理して | でつなぐ」というのがなんだか面倒ですね。

実はこの目的で使える Regexp.union という便利なメソッドがあります。
これは与えた引数(任意個数)が文字列のとき,それをエスケープ処理し,それらの選択を表す正規表現オブジェクトを作ってくれるものです。

こんなふうに動作します:

p Regexp.union("A+B", "3.14") # =>  /A\+B|3\.14/

これを使えば以下のように書けます。

def retrieve(text, words)
  words = words.sort_by{ -_1.length }
  text.scan(Regexp.union(*words))
end

簡潔でいいですね。

  1. そういう意味ではズルい出題でした。

  2. これは正規表現の一般論ではなく,Ruby の正規表現エンジン Onigmo の性質です。しかし,多くの正規表現エンジンがそうなっています。

  3. しかし,選択のあとにさらに検索パターンが続くとき,バックトラックによって一度見つかった選択肢が捨てられて次の選択肢が試されることはあります。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?