微妙に揺れのある次のような 二つの文字列リスト(画像ファイル名)があるとする。
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画像を作成しているので、 そこは考えなくて良い、とする。
もし、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 に変えておく。
この2つのリストを使って、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 関数をそのルールに対応したものに 差し換えてやれば ほかの部分のコードを修正しないで 対処できる。 つまり、myIntersection や myDifference に isEquals 関数(二つの文字列を渡して true か false を返す関数)を 渡せるようにすればよい。
だったら、そもそも自前実装などしないで、_.intersection や _.differecne の実装をそのまま使って、 isEquals 相当の関数を渡すことができればいいのでは?
おそらく、Underscore にそのような機能はない。 そして JavaScript の文字列の等価性の評価を この関数を使うときだけこのルール(つまり、ここで扱いたい表記の揺れを許すルール)にすることができれば よいのだろうけれど。そんなことはできるのだろうか? わからない。
Haskell のような言語ならそれは可能だろう。そのうち Haskell でこの問題を解いてみたい。
Liked some of this entry? Buy me a coffee, please.