微妙に揺れのある２つの文字列リストに対する積集合(Intersection)と差集合(difference)の計算

微妙に揺れのある次のような 二つの文字列リスト（画像ファイル名）があるとする。

const listA = ['grape.pdf', 'apple_v1.pdf', 'apple_v2.pdf', 'lemon_v1.pdf', 'peach_v2.pdf'];
const listB = ['grape.png', 'lemon.png', 'strawberry.png'];

listA の画像から listB の画像をPDFからPNG変換して作成した、という状況。 変換し忘れている画像ファイル(PDF)を知りたい。 そんな場合の計算方法について考える。 なお、世の常として listB に listA には存在しない strawberry が間違って混入されている、という例になっている。

これは例なのでサンプル数が少ない。だから答えは自明なのだが、もし件が 10000件 などとなれば計算機を使う必要がある。

見てのとおり、フルーツ名のついたPDFファイル（画像）リストだが、 場合によっては _v1 とか _v2 など のサフィックスが付いている。 画像変換作業者は _v2 などを見てもっともバージョンの大きい画像(PDF)を元にPNG画像を作成しているので、 そこは考えなくて良い、とする。

基本的には intersection して difference すればよい

もし、listA の画像ファイル名に揺れがなければ、話は簡単だ。 まずそんな理想的な場合の計算方法を考える。

//const listA = ['grape.pdf', 'apple_v1.pdf', 'apple_v2.pdf', 'lemon_v1.pdf', 'peach_v2.pdf'];
const listA = ['grape.png', 'apple.png', 'lemon.png', 'peach.png'];
const listB = ['grape.png', 'lemon.png', 'strawberry.png'];

intersection しないで直接 listA と listB の difference を求めても同じだが、ここでは積集合してから差集合をとることとする。

話を簡単にするために listA の各要素の拡張子も listB にあわせて png に変えておく。

この２つのリストを使って、listA からPNGに変換し忘れている画像はどれか（もう apple.png と peach.png であることは自明だが）を計算する。

const _ = require('underscore');

const listA = ['grape.png', 'apple.png', 'lemon.png', 'peach.png'];
const listB = ['grape.png', 'lemon.png', 'strawberry.png'];

const listCommon = _.intersection(listA, listB);
const result = _.difference(listA, listCommon);

console.log(result);

Underscore を使っています。

実行する。

$ node.js
[ 'apple.png', 'peach.png' ]

揺れのあるデータに対処する

では冒頭のデータに対処する方法を考える。

const listA = ['grape.pdf', 'apple_v1.pdf', 'apple_v2.pdf', 'lemon_v1.pdf', 'peach_v2.pdf'];
const listB = ['grape.png', 'lemon.png', 'strawberry.png'];

たとえば listA の各要素を _v1 や _v2 の部分を削除して、拡張子を pdf から png に変更したリストをつくり直して、それのリストを使って処理すればいいかもしれない。

このように:

const _ = require('underscore');

const listA = ['grape.pdf', 'apple_v1.pdf', 'apple_v2.pdf', 'lemon_v1.pdf', 'peach_v2.pdf'];
const listB = ['grape.png', 'lemon.png', 'strawberry.png'];

// listA の各要素を修正する.
const listA_ = _.map(listA, (item)=> {
    if( item.match(/([a-z]+)(_v\d)?\.pdf/) ){
        return `${RegExp.$1}.png`;
    } else {
        return item;
    }
});

const listCommon = _.intersection(listA_, listB);
const result = _.difference(listA_, listCommon);

console.log(result);

実行する。

$ node index.js
[ 'apple.png', 'apple.png', 'peach.png' ]

なんとなく apple と peach が抜けているというのはわかるが、 具体的に listAのどの画像ファイル(PDF)が処理漏れなのか、特定できない。 （今は数が少ないから特定はたやすいが、もし数が多かったら無理。）

つまり、listA に手を加えないままに intersection したり differnce する関数がほしい。

では intersection と difference を自前で実装しよう。

const roundFilename = (filename)=>{
    if( filename.match(/([a-z]+)(_v\d)?\.(pdf|png)/) ){
        return `${RegExp.$1}.png`;
    } else {
        return filename;
    }
};

const contains = (list,filename)=>{
    const isEquals = (filenameA, filenameB)=>{
        return ( roundFilename(filenameA) == roundFilename(filenameB) );
    };

    const filteredList = _.filter(list, (it)=> isEquals(it, filename));

    return ( filteredList.length>0 );
};

const myIntersection = (listA, listB)=>{
    return _.filter( listA, (filenameA)=> contains(listB, filenameA) );
};

const myDifference = (listA, listB)=>{
    return _.filter( listA, (filenameA)=> !contains(listB, filenameA) )
};

実行する。

$ node index.js
[ 'apple_v1.pdf', 'apple_v2.pdf', 'peach_v2.pdf' ]

できた。 これで、listA のどの画像ファイル(PDF)が処理漏れになっているかが明確になった。

結局 isEquals 関数が肝

表記の揺れがあっても同一画像ファイル名として扱いたい、ということだから比較する文字列（ここでは画像ファイル名）の等価性の評価をカスタマイズできればよい。それが isEquals 関数。 もし、許すべき表記の揺れルールが変更になった場合も、この isEquals 関数をそのルールに対応したものに 差し換えてやれば ほかの部分のコードを修正しないで 対処できる。 つまり、myIntersection や myDifference に isEquals 関数（二つの文字列を渡して true か false を返す関数）を 渡せるようにすればよい。

だったら、そもそも自前実装などしないで、_.intersection や _.differecne の実装をそのまま使って、 isEquals 相当の関数を渡すことができればいいのでは？

おそらく、Underscore にそのような機能はない。 そして JavaScript の文字列の等価性の評価を この関数を使うときだけこのルール（つまり、ここで扱いたい表記の揺れを許すルール）にすることができれば よいのだろうけれど。そんなことはできるのだろうか？ わからない。

Haskell のような言語ならそれは可能だろう。そのうち Haskell でこの問題を解いてみたい。