CodeIQ:ワイルドカード文字列を推定しよう

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「ワイルドカード文字列を推定しよう」(CodeIQ)を参照してください。

問題の概要

問題を引用します。
ファイルをマウスでぽちぽちと選択しながら、「これらと似たようなファイルを自動的に選択できないかなぁ…」と思った経験はありませんか?

もちろん、OSの標準機能としてワイルドカード文字列による検索は出来ますが、今回はそうではなく逆にユーザーが選んだ複数のファイルのパス名から、何をまとめて選びたいか意図を汲み取り、その結果をワイルドカード文字列として返すというプログラムを考えてみたいと思います。

本設問で求められるプログラムの前提条件は、以下の通りとなります。

標準入力から、ファイルパス名が、パス名の個数分複数行送られる
パス名は、制御コードを含まないASCII文字列で構成される
パス名の長さは、5文字(byte)以上20文字以下である
パス名の個数は、2個以上4個以下である

入力されるすべてのパス名の最長共通部分列(Wikipediaへのリンク)を求め、任意のパス名から最長共通部分列を除いた文字を'*'(アスタリスク)に置き換えたものを、ワイルドカード文字列とすること。

 ただしその際、ワイルドカード文字列内に'*'が連続する場合は、'*'1文字に置き換えること。

なお、最長共通部分列は必ず一意になることを前提とする。Wikipediaの例にもあるように、”ABC” と ”ACB” の最長共通部分列は ”AB” と ”AC” の両方であるが、そのような入力は与えられない。

また、ワイルドカードも必ず一意になることを前提とする。例えば、”ABBC”と”ABC”の期待されるワイルドカードは、”AB*C”と”A*BC”の両方となるが、そのような入力は与えられない。

求めたワイルドカード文字列を標準出力に送ること


入力出力
file01.txt
file02.txt
file11.txt
file*.txt
dir_a/doc_a.txt
dir_b/doc_a0.txt
dir_b/doc_a1.txt
dir_a/img_a.png
dir_*/*_a*.*

いかがでしょうか?
残りのファイルを自動的に選択するような機能はまだどのOSにも入っていないと思うのですが、こうしてみるとまだまだOSも賢くなれるような気がしませんか?
それでは、ぜひ挑戦してみてくださいね。

【問題】
標準入力から、複数のファイルパス名が、パス名の個数分複数行送られます。
似たような文字の並びのファイルを自動選択できるよう、入力されるすべてのパス名の最長共通部分列を用いて単一のワイルドカード文字列を求め、その結果を標準出力に返してください。

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

def getLcs(lcs, a, b, i, j, str)
	if (i == 0) || (j == 0) then
		return str
	end

	if a[i-1] == b[j-1] then
		str = a[i-1] + str
		ret = getLcs(lcs, a, b, i-1, j-1, str)
	else
		if lcs[i-1][j] >= lcs[i][j-1] then ret = getLcs(lcs, a, b, i-1, j, str)
		else ret = getLcs(lcs, a, b, i, j-1, str)
		end
	end

	return ret
end

def calcLcs(a, b)
	lcs = Array.new(a.size+1){ Array.new(b.size+1, 0) }

	for i in 1..a.size
		for j in 1..b.size
			if a[i-1] == b[j-1] then x = 1
			else x = 0
			end

			lcs[i][j] = [lcs[i-1][j-1] + x, lcs[i-1][j], lcs[i][j-1]].max
		end
	end

	return lcs
end

def padding(a, b)
	ret = ""
	i = 0

	for j in 0...b.size
		if i >= a.size then
			ret += '*'
		elsif a[i] == b[j] then
			ret += a[i]
			i += 1
		elsif a[i] == '*' then
			ret += '*'
			i += 1
		else
			ret += '*'
		end
	end

	if i < a.size then
		ret += a[i..-1]
	end

	return ret
end

def paddingAll(mstr, strs)
	padded = []
	for str in strs
		padded << padding(mstr, str).gsub(/\*+/, "*")
	end

	return padded.max{|a, b| a.size <=> b.size}
end

def solve(strs)
	sorted = strs.sort{|a,b| a.size <=> b.size}
	a = sorted.pop

	while !sorted.empty?
		b = sorted.pop

		lcs = calcLcs(a, b)
		a = getLcs(lcs, a, b, a.size, b.size, "")
	end

	ret = paddingAll(a, strs)
	return ret
end

# main
inputs = []
while line = gets
	line.strip!
	next if line.empty?

	inputs << line
end

puts solve(inputs)

解説

★★★の問題です。
難しいです。LCS(最長共通部分列)自体は調べればわかりやすい解説が見つかるのでそれほど問題ではありません。
問題は*にする部分を決める方法です。

考え方

問題にある通り、まずLCS(最長共通部分列)を求めます。
動的計画法でできます。
私は次のサイト最長共通部分列問題 (Longest Common Subsequence)を参考にしました。
説明は上記サイトが詳しいのでそちらを見てください。

LCSが分かっても、それをワイルドカードを含む文字列にするのが結構な難問です。
例えば、2つ目の例のLCSは"dir_/_a."ですが、これをどうやって"dir_*/*_a*.*"にするかです。
私は次の様な方法でやりました。

まず、LCSである"dir_/_a."と各入力値を1文字ずつ比べて、入力値にあってLCSにない文字の場所を*にします。
dir_a/doc_a.txt → dir_*/***_a.***
dir_b/doc_a0.txt → dir_*/***_a*.***
dir_b/doc_a1.txt → dir_*/***_a*.***
dir_a/img_a.png → dir_*/***_a.***

*が2以上の場所は*1個にします。
dir_a/doc_a.txt → dir_*/*_a.*
dir_b/doc_a0.txt → dir_*/*_a*.*
dir_b/doc_a1.txt → dir_*/*_a*.*
dir_a/img_a.png → dir_*/*_a.*

この中で最長の文字数のものを答えとします。

これであらゆる場合に正しいかは自信が有りません。

main

入力値を配列にしてsolve()に渡します。
戻り値を印字します。

solve(n, arr)

入力値を文字列の長さで昇順にソートします。
一番短いものをLCSの候補とし、2つ目以降とcalclcs()で比較してLCSを更新します。これを全ての入力値に対して行います。
LCSが決まったらそれと入力値の各文字列をpaddingAll()で比較して*を補充し、最も長い文字列を取得します。
これを答えとして返します。

calcLcs(a, b)

引数aはLCS候補、bは比較対象の文字列です。
aの文字列を行、bの文字列を列とした二次元配列を作ります。
この時、a,bの先頭は空けておいて、0行目と0列目は0で埋めます。
a="ac", b="abc"なら次の様になります。
a b c
0 0 0 0
a 0
c 0

行、列共に1からループし、斜め上の文字を比較します。
a[i-1]とb[j-1]が同じなら加算値x=1、そうで無ければx=0とします。
(i,j)の値をlcs[i-1][j-1] + x, lcs[i-1][j], lcs[i][j-1]のうち最大のものにします。

次の様になります。
a b c
0 0 0 0
a 0 1 1 1
c 0 1 1 2

getLcs(lcs, a, b, i, j, str)

claclcs()で作った表からLCSを作ります。
表の右下から左上に向かって同じ文字の場所を探すという方法でできます。

引数lcsはcalslcs()で作った表です。
a, bは2つの文字列です。
i, jはチェック対象の座標(i行, j列)です。
構築中のstrはLCS文字列です。

座標(0,0)になったら終わりなのでstrを返却します。

aとbの文字を比較し、同じならstrの先頭に追加し、i,jを1減らしてgetLcs()を再帰呼び出しします。
文字が違ったら、現在の座標の上か左のうちlscの値が大きい方に移動してgetLcs()を再帰呼び出しします(同値なら上)。

再帰呼び出しが戻ってきたらLCSが得られます。

paddingAll(mstr, strs)

mstrはLCS文字列です。
strsは入力値の文字列を長さで昇順にソートしたものです。

strsの各文字列strとmstrをpadding()で比較し、strに文字があってmstrにない場所を*で埋めた文字列を得ます。複数の*が並ぶ場所は正規表現を使って*1個にしてしまいます。
それをpaddedに保持し、paddedの中で最長のものを返します。

padding(a, b)

aはLCS文字列、bは入力値の文字列のうち1つです。
iは文字列aの現在フォーカスしている文字の位置、jはbの現在フォーカスしている文字の位置です。
retは*で埋められた文字列です。

bの文字列を1個ずつ見ながらaの文字と比較します。
i >= a.sizeの場合、つまりaの長さを超えた時は末尾に*が必要です。
a[i] == b[j]ならその場所は*ではなく特定の文字です。iを1増やしてaのフォーカス位置を進めます。
a[i] == '*'の場合、bの任意の文字と一致したことになるので*を増やし、aのフォーカス位置を進めます。
それ以外はaのフォーカス位置を動かさず、*を追加します。

ループを抜けた時、iがaの長さ未満なら評価されなかったaの部分文字列をretに加えます。

retを返却します。

雑感

LCSに関しては調べればわかったのでそれほど難しくはなかったのですが、*で埋めるのが難問でした。
diffでやっているのと同じことなんだろうと思って調べて見ましたがよくわからなかったので解答のような実装になりました。
パターンによってはダメな場合があるように思えてなりません。