Levenshtein Distance Search in Javascript

Levenshtein Distance Search Implementation in Javascript

Quick fuzzy search.

Generated by ChatGPT and modified by me.

Increasing the threshold to compare the response of findClosestSubstringDistance with make the search return more results.

This is roughly the same as the search used on this site, to search through posts without the need for a backend. This can be useful for static sites.

The effeciencey of this should be improved - I'm sure it is slow on large datasets.

Should also make sure the user has entered enough characters prior to displaying anything.

var searchInput = document.getElementById('searchInput');
var searchResults = document.getElementById('searchResults');

// Levenshtein Distance Function
function levenshteinDistance(a, b) {
    if (a.length === 0) return b.length; 
    if (b.length === 0) return a.length;
    var matrix = [];
    for (var i = 0; i <= b.length; i++) {
        matrix[i] = [i];
    }
    for (var j = 0; j <= a.length; j++) {
        matrix[0][j] = j;
    }
    for (var i = 1; i <= b.length; i++) {
        for (var j = 1; j <= a.length; j++) {
            if (b.charAt(i - 1) == a.charAt(j - 1)) {
                matrix[i][j] = matrix[i - 1][j - 1];
            } else {
                matrix[i][j] = Math.min(matrix[i - 1][j - 1] + 1,
                                        Math.min(matrix[i][j - 1] + 1,
                                                 matrix[i - 1][j] + 1));
            }
        }
    }
    return matrix[b.length][a.length];
};

function findClosestSubstringDistance(word, targetWords) {
    var minDistance = Infinity;
    targetWords.forEach(function(targetWord) {
        for (var i = 0; i <= targetWord.length - word.length; i++) {
            var substring = targetWord.substring(i, i + word.length);
            var distance = levenshteinDistance(word, substring);
            if (distance < minDistance) {
                minDistance = distance;
            }
        }
    });
    return minDistance;
}

searchInput.addEventListener('input', function() {
    var queryWords = searchInput.value.toLowerCase().split(' ');
    var filteredResults = [];

    postsData.forEach(function(post) {
        var postContentWords = (post.title + ' ' + post.content + 
            ' ' + post.headline + ' ' + 
            post.description).toLowerCase().split(/\s+/);
        var allWordsMatch = queryWords.every(queryWord => {
            return findClosestSubstringDistance(queryWord, postContentWords) <= 1;
        });

        if (allWordsMatch) {
            filteredResults.push(post);
        }
    });

    renderResults(filteredResults);
});

function renderResults(results) {

    searchResults.innerHTML = '';
    if(results.length){

        results.forEach(function(post) {
            var listItem = document.createElement('li');
            listItem.innerHTML = '<a href="' + post.url +
             '">' + post.title + '</a>';
            searchResults.appendChild(listItem);
        });
    }else{
        searchResults.innerHTML = 'No Results';
    }
}