ダジャレ力を磨くためには、日常に潜むダジャレを見つけ出す能力の成長が欠かせません。そこで、今回は文字列中からなるべく長いダジャレの文字列長を見つけ出すアルゴリズムについて考えます。
この記事は Qiita Engineer Festa 2022 (https://qiita.com/official-campaigns/engineer-festa/2022) および Qiita Engineer Festa アルゴリズム強化月間 (https://qiita.com/official-events/55631b864217a4df857a) のために書かれました。
tl;dr
ある文字列 $S$ に登場する最長のダジャレの文字列長を求めるには動的計画法を用いれば良いです。愚直解法の計算量 $\mathcal{O}(|S|^5)$ と比べて、動的計画法を用いた場合は $\mathcal{O}(|S|^2)$ とかなり高速です。
最長ダジャレ問題
次のような問題を最長ダジャレ問題と呼ぶことにします。この問題の解法について考えます。
ある文字列 $S$ の中に区間が重複することなく $2$ 回以上登場する部分文字列 $T$ の長さ $|T|$ の最大値を求めよ。
「あるみかんのうえにあるみかん」のような文字列は答えが $5$ になります。
「ふとんがふっとんだ」のような文字列は答えが $2$ ('とん' の部分) になってしまいます。一般的なダジャレの判定基準と異なることに注意してください。
愚直な解法
文字列 $S$ の全ての部分文字列に対して区間が重複しない部分文字列の列挙を行い、文字列一致判定を行います。
ある部分文字列と区間が重複しない部分文字列の列挙に $\mathcal{O}(|S|^2)$ ほどの計算量がかかり、文字列一致の判定には $1$ 回あたり平均 $\mathcal{O}(|S|)$ の計算量がかかります。これを全部分文字列 $\mathcal{O}(|S|^2)$ 個に対して行います。
したがって、全体として $\mathcal{O}(|S|^5)$ の計算量がかかってしまいます。
時間計算量 $\mathcal{O}(|S|^5)$ というのは、現代の計算機であれば $|S|\leq 50$ 程度なら数秒のうちに計算できるというレベルの計算量です。
高速な解法
動的計画法を使うと $\mathcal{O}(|S|^2)$ 程度の計算量で求められます。
部分文字列 $S_i, S_{i+1},...,S_{j-1}$ を $S[i: j]$ として表します。(Python のスライスと同じです)
$\mathcal{O}(|S|^2)$ というのは、現代の計算機であれば $|S|\leq 5000$ 程度なら数秒のうちに計算できるというレベルの計算量です。
$f_{i,j}$ を、 $S[i-d: i]$ と $S[j-d: j]$ が等しく、$[i-d:i)$ と $[j-d:j)$ が共通部分を持たないような $d$ の最大値とします。この $f_{i,j}$ を全てのありうる $i,j$ について求めて、その最大値をとったものがこの問題の答えとなります。
漸化式
$f_{i,j}$ を求める漸化式を作ります。
$i$ 文字目と $j$ 文字目が等しくて、$[i-f_{i,j}:i+1)$ と $[j-f_{i,j}:j+1)$ が共通部分を持たないなら、
$$f_{i+1,j+1}=f_{i,j}+1$$
のように更新できそうです。
$i$ 文字目と $j$ 文字目が等しくて、$[i-f_{i,j}:i+1)$ と $[j-f_{i,j}:j+1)$ が共通部分を持つなら、
$$f_{i+1,j+1}=f_{i,j}$$
です。そもそも $i$ 文字目と $j$ 文字目が等しくないなら、
$$f_{i+1,j+1}=0$$
となります。初期値は 0 としてよさそうです。
Python コード
簡単のため、$i \lt j$ としています。得られる答えは同じです。
def longest_dajare(S):
n = len(S)
f = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n):
for j in range(i + 1, n):
if S[i] == S[j] and j - f[i][j] >= i + 1: f[i + 1][j + 1] = f[i][j] + 1
if S[i] == S[j] and j - f[i][j] < i + 1: f[i + 1][j + 1] = f[i][j]
if S[i] != S[j]: f[i + 1][j + 1] = 0
return max((max(fi) for fi in f))
print(longest_dajare("あるみかんのうえにあるみかん"))
# 5
print(longest_dajare("ああああああああ"))
# 4
漸化式の定義通りに書いているので少し冗長ですね。
更なる高速なアルゴリズムへ……
Longest Duplicate Substring (no overlapping) などで調べると同じような問題で議論している人たちを見つけることができます。もっと速いアルゴリズム $\mathcal{O}(|S|\log^2|S|)$も見つかっているようです。
おわりに
今回は「最長ダジャレ問題」について扱いました。最初、Suffix Array と LCP Array で線形計算量になる気がしていましたが、区間の重複が出るのでボツになりました。（3000文字書いてから気付いて絶望した……。）結果的にパワー感がちょっと足りない感じになってしまいました。
「ふとんがふっとんだ」を「ふとん」に関するダジャレとして検出しようとするのは自然言語処理の分野になるのかなと思います。こちらが検出できた方がダジャレ検出っぽくはあるのですが……。