Idea: permutate()

Question

Idea: permutate()

Toflar opened this issue 7 years ago · 2 comments

I need to implement a "Did you mean ....?" functionality which you usually achieve using the levenshtein() function. But in that case I would need to search a database for possible matches. So given I have a search string foobar, I need all possible permutations to execute a LIKE query 😄

So I imagine this:

$permutations = s('foobar')->permutate();

// $permutations is now an array of "foobra", "foorba", "barfoo" etc. pp.

A cool addition to that would be an optional $maxLevenshteinDistance parameter. Like so:

$permutations = s('foobar')->permutate(2);

// $permutations should contain "foobra" (distance of 2) but not "barfoo" (distance of 7)

Do you see that fitting in this library? It's string manipulation, it just doesn't return a modified string. But chars() and others don't do that either :)

Answer 1 · 2017-12-06T15:09:37.000Z

While trying to make a PR for this, I noticed that even for short words, there are obviously thousands and thousands of permutations possible and calculating them takes forever 😄 So probably not the best idea but fiddling with it was interesting :)

Answer 2 · 2017-12-10T22:59:59.000Z

I don't think enumerating all permutations in the query itself is the right idea for this. Fuzzy search should probably be done with your DB, e.g.

pg_trgm with postgresql https://www.rdegges.com/2013/easy-fuzzy-text-searching-with-postgresql/
fuzzy/fuzziness in elaticsearch https://www.elastic.co/guide/en/elasticsearch/reference/current/query-dsl-fuzzy-query.html

But sounds like you came to that conclusion as well! :)