読者です 読者をやめる 読者になる 読者になる

CodeIQ Blog

自分の実力を知りたいITエンジニア向けの、実務スキル評価サービス「CodeIQ(コードアイキュー)」の公式ブログです。

エンジニア夏祭り2013「このお店とこのお店は同じ店?!」解答編 #engineer #matsuri #hatena #ruby #夏祭り #夏の想い出

CodeIQの中の人、OL元帥です。

「はてな」さんとCodeIQがタッグを組んだ『CodeIQ×はてな エンジニア夏祭り2013』
第1夜「はてなからの挑戦状」
f:id:codeiq:20130725181204j:plain

株式会社想創社 えふしん さんから届きました、
Rubyの問題の解答・解説を公開します!


f:id:codeiq:20130809203823j:plain



◇◇◇◇◇◇◇◇◇◇


CodeIQ公式ブログをご覧の皆さんこんにちは。えふしんです!
今回出題させていただいた問題の解答を書きます。
いただいた解答については、想像以上に質が高く、CodeIQさんのユーザー層の厚さに驚いております。

課題
────────────────────────────────────────
以下に示す「お店」に該当するお店を「対象対象文字列」の候補から抽出してください。
ここにないテストケースにおいても同じロジックで動作することを想定してコードを書いて下さい。

ケース1 「中目黒いぐち」

調査対象文字列
・焼鳥 中目黒 いぐち
・串若丸 本店 くしわかまる
・鳥よし 中目黒店 とりよし

正解 「焼鳥 中目黒 いぐち」

ケース2 「まるかつ水産 東京ミッドタウン店」
調査対象文字列
・まるかつ水産 東京ミッドタウン店
・まるかつ食堂 東京ミッドタウン店
・東京ミッドタウン店 アンリ・ルルー
・浅野屋 東京ミッドタウン店

正解「まるかつ水産 東京ミッドタウン店」

ケース3 「寿司寿」
調査対象文字列
・六本木 寿司寿
・寿し処 寿々 すず - 溜池山王/寿司
・松葉寿し まつばずし - 六本木一丁目/寿司

正解「六本木 寿司寿」

────────────────────────────────────────

最初にお詫びですが、解答いただいた方には、若干、例題に一部不備があり失礼しました。
もっといやらしい問題を考えていたら、一周回って元の文字列と候補文字列が同じ文字列になってしまい1つだけ平凡な問題になってしまったのは、うっかりミスであります。

さて僕の解答ですが、2つの文字列の共通の部分列を抽出する最長共通部分列 LCS(Longest Common Subsequence) を求めるライブラリを使ってみました。

解答例:

# -*- encoding: UTF-8 -*-
require "diff/lcs"

def getSimilarScore(str1 , str2)
    seq1 = str1.split(//)
    seq2 = str2.split(//)
    lcs = Diff::LCS.LCS(seq1 , seq2)
    return lcs.size * 2.0 / (seq1.size + seq2.size);
end

def getSimilarShop(src , shopList)
    return shopList.max_by {|dest|  getSimilarScore(src , dest) }
end

puts getSimilarShop("中目黒いぐち" , ["焼鳥 中目黒 いぐち","串若丸 本店 くしわかまる","鳥よし 中目黒店 とりよし"])
puts getSimilarShop("まるかつ水産 東京ミッドタウン店" , ["まるかつ水産 東京ミッドタウン店","東京ミッドタウン店 まるかつ食堂 ","東京ミッドタウン店 アンリ・ルルー","浅野屋 東京ミッドタウン店"])
puts getSimilarShop("寿司寿" , ["六本木 寿司寿","寿し処 寿々 すず - 溜池山王/寿司","松葉寿し まつばずし - 六本木一丁目/寿司"])

────────────────────────────────────────
実行結果

焼鳥 中目黒 いぐち
まるかつ水産 東京ミッドタウン店
六本木 寿司寿
────────────────────────────────────────

getSimilarScoreメソッドは、Diff::LCS.LCSを使って、2つの文字列の一致する文字列を抽出し、最後に、一致度合いを比較しスコアとして返します。
getSimilarShopは、お店の比較候補をgetSimilarScoreで比較し、スコアが最大となるお店の名前を抽出しています。

コードは、たったこれだけです。Diff::LCSのライブラリを提供してくだった方に感謝です。
diff機能を作りたい時に差分抽出も簡単にできるのでマイナーな割には強力なライブラリだと思います。

LCSを求めるライブラリは以下のURLを参照ください。
diff-lcs | RubyGems.org | your community gem host

LCSのアルゴリズムについては、たつをのChangeLogの山下達雄さんや、伊藤直也さんのblog記事を始めとして、検索していただくと多数の記事が見つかります。

Algorithm::Diff で類似文字列検索

最長共通部分列問題 (Longest Common Subsequence) - naoyaのはてなダイアリー

また類似のアルゴリズムとして、 編集距離(Edit Distance)を評価値としたDPマッチングという手法もあります。

こちらの方法は、一方の文字列を文字の挿入や削除、置換によって、もう一方の文字列と一致させた場合に必要な手順の最小回数を求めたものを評価することになります。

[を] Dynamic Programming による類似文字列マッチの実装例

レーベンシュタイン距離 - Wikipedia



さて、いただいた解答の方ですが、hm001さん、Muさんがレーベンシュタイン距離をご自身で書かれていたコードが印象的でした。

Muさんのコードを参考までに引用いたします。

#! /usr/bin/ruby

# レーベンシュタイン距離
def levenshtein( s1, s2)
  d = (0..s1.size).to_a
  s2.size.times{|y|
    n = [y]
    s1.size.times{|x|
      n[x+1] = [d[x] + (s1[x]==s2[y] ? 0 : 1), d[x+1] + 1, n[x] + 1].min
    }
    d = n
  }
  d[-1]
end

# レーベンシュタイン距離最小の文字列を探す
def nearest( target, list)
  list.min_by{|s| levenshtein(s,target)}
end

#【ケース1】
puts nearest( '中目黒いぐち', 
 ['焼鳥 中目黒 いぐち',
  '串若丸 本店 くしわかまる',
  '鳥よし 中目黒店 とりよし'])

#【ケース2】
puts nearest( 'まるかつ水産 東京ミッドタウン店',
 ['まるかつ水産 東京ミッドタウン店',
  'まるかつ食堂 東京ミッドタウン店',
  '東京ミッドタウン店 アンリ・ルルー',
  '浅野屋 東京ミッドタウン店'])

#【ケース3】
puts nearest( '寿司寿',
 ['六本木 寿司寿',
  '寿し処 寿々 すず - 溜池山王/寿司',
  '松葉寿し まつばずし - 六本木一丁目/寿司'])


なおレーベンシュタイン距離の算出ができるライブラリも存在していますので、
こちらを使うのも手です。maehrmさんの解答を引用いたします。

# -*- coding: utf-8 -*-
require 'levenshtein'

def solv(original, strings)
  strings.map! {|s|
    {
      val: Levenshtein.normalized_distance(original, s),
      str: s
    }
  }
  strings.min_by {|e| e[:val]}[:str]
end

# ケース1
puts solv("中目黒いぐち", ["焼鳥 中目黒 いぐち", "串若丸 本店 くしわかまる", "鳥よし 中目黒店 とりよし"])
# ケース2
puts solv("まるかつ水産 東京ミッドタウン店", ["まるかつ水産 東京ミッドタウン店", "まるかつ食堂 東京ミッドタウン店", "東京ミッドタウン店 アンリ・ルルー", "浅野屋 東京ミッドタウン店"])
# ケース3
puts solv("寿司寿", ["六本木 寿司寿", "寿し処 寿々 すず - 溜池山王/寿司", "松葉寿し まつばずし - 六本木一丁目/寿司"])

また、amatchのライブラリでもレーベンシュタイン距離の算出ができるようです。shoprevさんの回答を以下に引用いたします。

# coding: utf-8
require 'amatch'
class Levenshtein
	def initialize(array)
		@array=array
	end
	def find(target)
		result=""
		mostsimilar=0
		@array.each do |it|
			similar=target.levenshtein_similar(it)
			if similar > mostsimilar
				mostsimilar=similar
				result=it
			end
		end
		result
	end
end
problem=[
{:store=>"中目黒いぐち",:target=>["焼鳥 中目黒 いぐち","串若丸 本店 くしわかまる","鳥よし 中目黒店 とりよし"]},
{:store=>"まるかつ水産 東京ミッドタウン店",:target=>["まるかつ水産 東京ミッドタウン店","まるかつ食堂 東京ミッドタウン店","東京ミッドタウン店 アンリ・ルルー","浅野屋 東京ミッドタウン店"]},
{:store=>"寿司寿",:target=>["六本木 寿司寿","寿し処 寿々 すず - 溜池山王/寿司","松葉寿し まつばずし - 六本木一丁目/寿司"]},
]
problem.each_with_index do |it,i|
	print <<EOS
【ケース#{i+1}
お店:
#{it[:store]}
正解:
#{Levenshtein.new(it[:target]).find(it[:store])}

EOS
end


レーベンシュタイン距離を求めるライブラリは以下をご確認ください。
levenshtein | RubyGems.org | your community gem host
amatch | RubyGems.org | your community gem host

また、その他の方もN-グラム生成関数を作られていたり、シンプルなところでは一致する文字列をカウントしていたりと、大体やってることは似たようなところを目指していると思うのですが、大変勉強になりました。レーベンシュタイン距離を採用している方が多かったようなので、そっちを採用した方がよさそうですね。

こういうのは情報系学科出身の方以外は、なかなか知る機会もない気がするのですが(僕は情報系ではない)、ここで紹介したものは、特にWeb系の方には、非常に実用性の高いアルゴリズムなので是非キャッチアップしてみてください。


◇◇◇◇◇◇◇◇◇◇


いかがでしたか?
挑戦者のいろいろな解答が見られて勉強になりますね!
えふしんさんの「もっといやらしい問題」というのが気になりますが…


第1夜「はてなからの挑戦状」、たくさんの方に挑戦していただき本当に嬉しいです!
ありがとうございました!



CodeIQ × はてな エンジニア夏祭り19113 第2夜 ブログでわっしょい開催中!
f:id:codeiq:20130806104304g:plain
「納涼!ほんとにあった怖いコード」「CodeIQの問題・パズルを考えよう!」のいずれかのお題でブログを書くと、豪華審査員が選評してくれます。
詳しくはキャンペーンページヘ!



エンジニアのための新しい転職活動!CodeIQのウチに来ない?の特集ページを見る