Matching windows with EMD (Earth Mover Distance) #55
Description
Current implementation seems to employ a greedy strategy when it comes to matching windows to saved windows (previous/saved session) when opening multiple windows at once (e.g., when Firefox opens all previous windows). A better strategy could be to use something like the EMD (Earth Mover Distance - Kantorovich Rubinstein Distance) to match all unmatched windows to saved windows.
Example (generated with ChatGPT):
'use strict';
import { SETTINGS_KEY_MATCH_THRESHOLD } from './settings'; // Assume this is your constants file
import { levensteinDistance } from './distance'; // Assume this is your Levenshtein function
import { Munkres } from 'munkres-js'; // Hungarian Algorithm implementation
/**
* Compute the cost matrix for window matching.
* @param {Array<Object>} savedWindows - List of saved windows from the old session.
* @param {Array<Object>} currentWindows - List of currently open windows.
* @returns {Array<Array<number>>} - Cost matrix.
*/
function computeCostMatrix(savedWindows, currentWindows) {
return savedWindows.map(savedWindow => {
return currentWindows.map(currentWindow => {
let titleDist = levensteinDistance(savedWindow.title, currentWindow.title);
let titleScore = (savedWindow.title.length - titleDist) / savedWindow.title.length;
let positionCost = savedWindow.position !== currentWindow.position ? 1 : 0; // Example: binary penalty
let workspaceCost = savedWindow.workspace !== currentWindow.workspace ? 1 : 0;
// Combine costs: Adjust weights as necessary
return 1 - titleScore + positionCost + workspaceCost;
});
});
}
/**
* Match saved windows to current windows using the Hungarian algorithm.
* @param {Array<Object>} savedWindows - List of saved windows.
* @param {Array<Object>} currentWindows - List of current windows.
* @returns {Array<Object>} - List of matched window pairs.
*/
function matchWindows(savedWindows, currentWindows) {
let costMatrix = computeCostMatrix(savedWindows, currentWindows);
let munkres = new Munkres();
let assignments = munkres.compute(costMatrix);
let matches = assignments.map(([savedIndex, currentIndex]) => {
let cost = costMatrix[savedIndex][currentIndex];
if (cost <= 1 - SETTINGS_KEY_MATCH_THRESHOLD) { // Respect the match threshold
return {
savedWindow: savedWindows[savedIndex],
currentWindow: currentWindows[currentIndex],
cost: cost
};
}
return null; // No valid match
});
// Filter out invalid matches
return matches.filter(match => match !== null);
}
// Example usage
let savedWindows = [
{ title: 'Document 1', position: '0,0', workspace: 1 },
{ title: 'Document 2', position: '1,1', workspace: 2 }
];
let currentWindows = [
{ title: 'Document 1', position: '0,0', workspace: 1 },
{ title: 'Document 2 (Edited)', position: '1,1', workspace: 2 }
];
let matchedWindows = matchWindows(savedWindows, currentWindows);
console.log(matchedWindows);