データのJOINと言えば、複数のデータセットをあるキーで完全一致するものですが、まれに、完全一致するようなレコードがあればそれと結合したいが、そのようなものがない場合でも、キーのフィールドの値のN文字以上の前方一致で最長の一致となるものがあればそのようなレコードと結合したいというケースに出くわすことはないでしょうか？

例えば、geohashでエリア名を規定している対応表に該当するデータセットがあるものの、対応表でメンテしているgeohashの粒度(精度)はエリアによってまちまちであるため、あるgeohash値でルックアップして、完全一致する値が対応表にあればそれを使うものの、そうでなければ、上位桁数に絞って一致する次善の対応値を使うというような例です。

件名のとおり、mapやreduce、filterを使うといい感じに記述できそうな気がしたので試してみた...というのがこの記事です。

考え方

2つのデータセットのうち、ルックアップされる側のデータを結合フィールドの最初の数文字からなるtrie風のデータにあらかじめ変換したものを用意して、これをハッシュとみなして検索し、得られたハッシュの中のtrieの内訳データを探索するやり方としました。

なお、実際のところ汎用化や一般化には至らなかったので、インプットデータ等に仮定をおいて取り扱う「問題」を限定してあります。（インプットデータのところにもう少し「仮定」に関する考え方を補足してあります。）

この類の仮定を置いていいなら、また言語の機能を使うなどすればもっとスマートな方法がいくらでもありそうです。

今のところこんな感じのものどまりですが、ゼロから考えるよりは時間短縮になるのと記録しておけばいつかもっとスマートな方法に巡り会えるかもしれないのでここにメモっています。

なお、この記事は以下の記事の続きでもあるのですが、よく見たら、mapは使っているもののという例にすぎないかも。

itdepends.hateblo.jp

インプットデータ(プログラム前半)

'use strict';

/*
2つのデータを「ゆるJOIN」するサンプル

＊「ゆるJOIN」
    二つのデータセットをキーとなるフィールドで結合するが、前方一致で一致する部分が最長のもので結合する。
    データAとデータBがあり、Aの12345というキーを持つレコードを、Bに12345があればそれと結合するが、なければ1234*にあてはまるものを結合する。

＊　汎用は辛いので、データセット等に次の仮定をおく。    
    1. Aを左結合とする演算に限定。
    2. キーとなるフィールドの桁数はAとBで同じ。また、桁数は固定とする。
    3. 最初のN桁目までが一致するようなものがなければ結合失敗とするような歯止めのNを要件として定めることができる。
        (言い換えると、BのキーフィールドのN桁目部分の集合は、Aの同様なものの集合を含んでいることが保証されているものを対象にしてある)

*/

//注：文字列か数字かということはポイントではないので、タイピング量を減らすことを優先、つまり型は雑に扱っている。

const a = ['12345','12344','67890','34567','345XX'];
const PRESIZE = 3;
const SIZE = 5;
// trie風のデータ。これを作るところはまた別途。
const b = {
    12345: { k: [''], p: [11111] },
    123: { k: ['45', '4',], p: [11111, 1111], default: 123 },
    67890: { k: [''], p: [22222] },
    678: { k: ['90', '9'], p: [22222, 2222], default: 678 },
    345: { k: ['66', '6'], p: [33333, 3333], default: 345 },
};

/*
↓ aとbを用いて得られる(得たい)出力のイメージ

[
    [ '12345', 11111 ],
    [ '12344', 1111 ],
    [ '67890', 22222 ],
    [ '34567', 3333 ],
    [ '345XX', 345 ]
]

*/

関数(プログラム後半)


/*
edgeNGram('abcde') ->
['abcde','abcd', 'abc', 'ab', 'a']
*/
const edgeNGram = str => {
    const it = [...Array(str.length).keys()].reverse();
    return it.map(i => str.substr(0, i + 1));
};

/* ゆるJOINロジック */
const aa = a.map(el => {
    if (b[el]) {
        return [el, b[el].p[0]];
    }
    const prfx = el.substr(0, PRESIZE);
    const sufx = el.substr(PRESIZE);
    const sufxs = edgeNGram(sufx);
    /*
    // これは例外をあげた方が良い類だが、今回は発生しえない扱い
    if (!b[prfx]) {
        console.log('failed');
        return null;
    }
    */
    const t = b[prfx];
    for (const sx of sufxs) {
        const idx = t.k.findIndex(x => x === sx);
        if (idx > -1) {
            return [el, t.p[idx]];
        }
    }
    return [el, t.default];
});
console.log(aa);

プログラム(hoge.jsと命名) 実行結果

$ node hoge.js 
[
  [ '12345', 11111 ],
  [ '12344', 1111 ],
  [ '67890', 22222 ],
  [ '34567', 3333 ],
  [ '345XX', 345 ]
]

はてだBlog（仮称）

ゆるJOIN（JavaScriptでもmapやreduce、filter（手習いメモ) その3）

考え方

インプットデータ(プログラム前半)

関数(プログラム後半)

プログラム(hoge.jsと命名) 実行結果