以下の標準化編集距離が一定以下のペアを全列挙する問題を考えます。
$X:$ 文字列の集合、 $\varepsilon$ : 類似度の閾値, $f_e: X\times X \to [0,1] $ : 標準化編集距離
$$
find \ \max_{S \subset X \times X} \ (y,z) \in S \ {\rm s.t.} \ f_e(y,z) \le \varepsilon
$$
(標準化)編集距離についての記事は多数存在しますが、例えば wikipedia を参照ください。
全ペア計算すれば求めることは可能ですが、より高速に(取りこぼしがなく)全列挙する方法を考えます。
$\forall x,y \in X$ に対し、$g(x,y) \le f_e(x,y)$ を満たすような $g: X\times X \to [0,1]$ を定義できた時
(1) $g(x,y)$ の値を先に計算
(2-a) $g(x,y) > \varepsilon$ を満たすとき、$f_e (x,y) > \varepsilon$が成立するため、 $f_e(x,y)$ の値を計算した上で $\varepsilon$ との大小比較を行う必要がない.
(2-b) $g(x,y)\le \varepsilon $ を満たすとき、$f_e (x,y)$ と $\varepsilon $ の大小関係は不明であるため、 $f_e(x,y)$ の値を計算し、 $\varepsilon$ との大小比較を行う
下記の２つの条件を共に満たす場合のみこのアプローチは有効となります。
- (2-b) の条件を満たすペアが (2-a) の条件を満たすペアより十分少ない
- $f_e$ に比べ $g$ が十分高速に計算可能
具体的な取り方の例)
$g : X\times X \to [0,1]$ を以下のように定義する.
$\forall x \in X$ , $C_x$ : $x$ で使われる文字列の集合 と定義する.
Ex) $x$ = "TOKYO" の時, $ C_x = \{T, O, K, Y \}$
$$
g(x,y) := \frac{\max \{|C_x \setminus C_y|, |C_y \setminus C_x|\}}{\max\{|x|, |y| \}}
$$
$\forall x,y \in X$ に対し、$g(x,y) \le f_e(x,y)$ を満たす.
(イメージ: 異なる文字は置換/削除の必要があるためコストを要する.)
この $g$ は $f_e$ に比べ高速に計算可能である。
- $f_e(x,y)$ の計算量: $O(|x| |y|)$
- $g(x,y)$ の計算量: $O(\max\{|x|, |y| \})$
例1) $x =$ "バナナ" , $y=$ "バハマ" の時
$f_e(x,y) = \frac{2}{3}$
$C_x = \{バ, ナ \}, C_y = \{ バ、ハ、マ \} $
$g(x,y) = \frac{2}{3}$
$g(x,y) \le f_e(x,y)$ を満たす.
例2) (等号成立しない例) $x =$ "トウキョウ" , $y=$ "キョウト" の時
$f_e(x,y) = \frac{3}{5}$
$C_x = \{ト, ウ, キ, ョ \}, C_y = \{ ト, ウ, キ, ョ \} $
$g(x,y) = 0$
$g(x,y) \le f_e(x,y)$ を満たす.
上記の方法が妥当であること(取りこぼしがないこと)は下記の補題により保証されます。
$X: set, f_e : 標準化編集距離$, $g(x,y) := \frac{\max \{|C_x \setminus C_y|, |C_y \setminus C_x|\}}{\max\{|x|, |y| \}}$ に対し、$\forall x, y \in X, g(x,y) \le f_e(x,y)$ が成立する.
(証明)
文字列の結合を＊で表現する。
$T$: 文字の集合を受け取り、要素をUnicodeの若い順に１文字ずつ並べた文字列を返す写像 とする. (Unicode順に特に意味はないです)
Ex) $C = \{y,s,d\}$ の時, $T(C) = $ "dsy"
$x,y$ に含まれる共通の文字を並べた文字列を $z$ とおく.
$x,y$から $z$ に含まれる文字を抜いた文字列を $\bar{x}, \bar{y}$ とおく.
\begin{align}
g(x,y) &= \frac{1}{\max\{|x|, |y| \}} \max\{|C_x\setminus C_y|, |C_y\setminus C_x| \}
\\
&\le f_e ( T(C_x\setminus C_y), T(C_y\setminus C_x)) \\
&= f_e(z * T(C_x\setminus C_y), z*T(C_y\setminus C_x)) \\
&\le f_e(z*\bar{x}, z*\bar{y}) \\
&\le f_e(x,y)
\end{align}
この例のように適当な関数の値が一定以上(以下)のペアを高速に抽出したい場合はそれを下から抑えるor上から抑える関数を探してみてください。
謝辞: 議論に参加していただいた研究室の皆様、感謝申し上げます。