bms-min-hasher

BMS譜面の帰属本体類似度を算出するために使用できる MinHash の仕様および実装です。
譜面同士の MinHash を比較することで、同じ本体から派生している「らしさ」を得ることができます。

このプロジェクトでは MinHash 算出の手順と各種定数を 仕様化 し、Node.js および golang における実装とテストを備えることで統一された MinHash の算出方法を提供します。

仕様

SPEC.md を参照してください。

ライブラリとしての利用

仕様を必要とせず、入力に対する結果のみが必要な場合は下記の手順で使用できます。

npm install @bmssearch/bms-min-hasher

MinHash を得る手順

import {
  ConventionalBmsFeatureTokensExtractor,
  hashTokens,
  computeMinHash,
} from "@bmssearch/bms-min-hasher";
import fs from "node:fs/promises";

const buf = await fs.readFile("bms/file/path.bme"); // BMSファイルのバイナリを読みこむ

// 従来BMS（bmsonでない）から特徴文字列を抽出するモジュール
const extractor = new ConventionalBmsFeatureTokensExtractor();
const featureTokens = await extractor.extract(buf);

// MinHash 計算のため、特徴文字列をハッシュ化し uint32 の配列を得る
const hashedTokens = await hashTokens(featureTokens);

// MinHash を得る
const minHash = computeMinHash(hashedTokens);

console.log(minHash); // eg. [8069152,8482535,54284318,34004118,13351918, ...]

類似度の比較

import {similarity} from "@bmssearch/bms-min-hasher";

const sim = similarity(minHash1, minHash2); // eg. 0.62

ひとつの MinHash をもとに、データベースから類似する MinHash を検索するようなユースケースでは LSH と呼ばれる手法が有効です。