Power Queryで文字列同士の類似度を求める

Power Queryで文字列同士の類似度を得る方法はないかと、

• レーベンシュタイン距離を実装してみたり
• Power QueryのFuzzyJoin(曖昧結合)関数の結果から逆算しようとしてみたり

と色々試してはみたものの、安定しなかったり重すぎたりで実用には厳しそう。
そこで、こんなのを作ってみました。

処理手順

各文字列について、含まれる文字を

• 文字そのもの(char)
• 文字列内での登場回数(occ)
• 文字列内での位置(idx)

という3列のテーブルで表現する。「Qualia」と「Qiita」なら次のようになる。

char	occ	idx
Q	1	0
u	1	1
a	1	2
l	1	3
i	1	4
a	2	5

char	occ	idx
Q	1	0
i	1	1
i	2	2
t	1	3
a	1	4

行数の多いほうを左表として、charとoccで左外部結合する。

char	occ	idx	char	occ	idx
Q	1	0	Q	1	0
u	1	1	null	null	null
a	1	2	a	1	4
l	1	3	null	null	null
i	1	4	i	1	1
a	2	5	null	null	null

各行について、長い方の文字列の文字数を満点として、idxの差の絶対値を減点したスコアを求める。
ただし、nullの場合は0点とする。

char	occ	idx	char	occ	idx	score
Q	1	0	Q	1	0	6
u	1	1	null	null	null	0
a	1	2	a	1	4	4
l	1	3	null	null	null	0
i	1	4	i	1	1	3
a	2	5	null	null	null	0

scoreの合計を満点だった場合のスコアで割ったものを類似度とする。

(6 + 4 + 3) / (6 * 6) = 0.36111...

Power Queryでの実装例

TextSimilarity.pq

let
	fx = (s as nullable text) => (t as nullable text) as nullable number =>

	if (List.Contains({s, t}, null)) then null
	else if s = t then 1 
	else if List.Contains({s, t}, "") then 0
	else if Text.Length(s) < Text.Length(t) then @fx(t)(s)
	else

	let
		join = Table.NestedJoin(
			TextDetail(s), {"char" ,"occ"},
			TextDetail(t), {"char" ,"occ"},
			"t",
			JoinKind.LeftOuter
		),
		expand = Table.ExpandTableColumn(
			join,
			"t",
			{"idx"},
			{"t.idx"}
		),
		maxLength = Text.Length(s),
		add = Table.AddColumn(
			expand,
			"score",
			each if [t.idx] = null then
				0
			else
				maxLength - Number.Abs([idx] - [t.idx]),
			type number
		)
	in
		List.Sum(add[score]) / Number.Power(maxLength, 2)
in
	fx

TextDetail.pq

(text as text) as table =>
let
	table = #table(
		type table [char = text, occ = Int32.Type, idx = Int32.Type],
		{}
	)
in
	List.Accumulate(
		Text.ToList(text),
		table,
		(state, current) => Table.InsertRows(
			state,
			Table.RowCount(state),
			{[
				char = current,
				occ = Table.RowCount(Table.SelectRows(state, each [char] = current)) + 1,
				idx = Table.RowCount(state)
			]}
		)
	)