JS - Is there a more efficient way to compare values in an array to a target search term-CodePudding

I am aiming to search an array of objects for one that's title is similar or matches a search term exactly. The problem is I would like to prioritise exact matches over matches that only contain the string.

The current code does this by looping multiple times, each time with a different condition, and returns the object if it matches.


class Item {
    constructor(title) {
        this.title = title;
    }
}

function findMatch(term) {
    const items = [new Item("term"), new Item("Longer Term"), new Item("Completely Different Title")];

    // Check if any match the search term exactly
    for (var item of items) {
        if (item.title === term) return item;
    }

    // Check if any match the search term, ignoring case
    for (var item of items) {
        if (item.title.toLowerCase() === term.toLowerCase()) return item;
    }

    // Check if any start with the search term
    for (var item of items) {
        if (item.title.toLowerCase().startsWith(term.toLowerCase())) return item;
    }

    // Check if any end with the search term
    for (var item of items) {
        if (item.title.toLowerCase().endsWith(term.toLowerCase())) return item;
    }

    // Check if any contain the search term
    for (var item of items) {
        if (item.title.toLowerCase().includes(term.toLowerCase())) return item;
    }
    
    return null;
}

console.log(findMatch("different")); // Item with title "Completely Different Title"

Is there a way to do this more efficiently, like in one loop - or is there a better way to search strings?

I have looked into using the Levenshtein algorithm however this does not work for searching "Comp" and getting the Item with title "Completely Different Title", as a lot more is different between "Comp" and "Completely Different Title" than there is between "Comp" and "term" - Is there a way to incorporate the same idea into this search?

CodePudding user response：

If you're looking for efficiency, the only improvement I can think of that would reduce processing would be to lowercase the strings in advance, instead of lowercasing each value inside each loop. Though, it'd probably be a very marginal improvement and be unnoticeable in most cases.

class Item {
    constructor(title) {
        this.title = title;
        this.lowerTitle = title.toLowerCase();
    }
}
function findMatch(term) {
    const lowerTerm = term.toLowerCase();
    // use item.lowerTitle and lowerTerm when appropriate

The logic you want to implement fundamentally requires a loop over all elements looking for one condition, followed by another loop over all elements looking for another, etc. So there's no real way to improve the computational complexity over your current implementation.

You could combine some or all of the conditions with a regular expression, but that would break the priority sequence of match types to be returned.

If you want to make the code shorter and easier to maintain, that's easy enough - you could use an array of callbacks that get called for every item in order:

const comparers = [
  (a, b) => a === b,
  (a, b) => a.startsWith(b),
  (a, b) => a.endsWith(b),
  (a, b) => a.includes(b),
]
for (const fn of comparers) {
  if (fn(item.lowerTitle, lowerTerm)) return item;
}

Is there a way to incorporate the same idea into this search?

Checking the Levenshtein distance would be a bit different. Instead of looping over items and returning one when it matches, you'd need to loop over all items unconditionally and return the best match after the loop finishes.

let bestItem;
let lowestDistance = Infinity;
for (const item of items) {
  const dist = compare(item.lowerTitle, lowerTerm);
  if (dist < lowestDistance) {
    bestItem = item;
    lowestDistance = dist;
  }
}
return bestItem;

You'd do this at least instead of the .includes check at the end. Depending on what logic you want, you might also remove the startsWith and endsWith checks in exchange too.

CodePudding user response：

You might assign a score to your items depending on "similarity" whatever it is, then filter and sort the items by that score and return the matches:

class Item {
  constructor(title) {
    this.title = title;
  }
}
const items = [new Item("term"), new Item("Longer Term"), new Item("Completely Different Title")];

function findMatch(term) {
  for (var item of items) {
    // Check if any match the search term exactly
    if (item.title === term) item.score = 10000;

    // Check if any match the search term, ignoring case
    else if (item.title.toLowerCase() === term.toLowerCase()) item.score = 1000;

    // Check if any start with the search term
    else if (item.title.toLowerCase().startsWith(term.toLowerCase())) item.score = 100;

    // Check if any end with the search term
    else if (item.title.toLowerCase().endsWith(term.toLowerCase())) item.score = 10;

    // Check if any contain the search term
    else if (item.title.toLowerCase().includes(term.toLowerCase())) item.score = 1;
  }
  return items.filter(i => 0 < i.score).sort((a, b) => b.score - a.score).map(i => delete i.score && i)
}

console.log(findMatch("different")); // Item with title "Completely Different Title"
console.log(findMatch("term"));