search

awslabs / aws-shell

An integrated shell for working with the AWS CLI.
Apache License 2.0
7.18k stars 772 forks source link

Fix fuzzy search algorithm #5

Open jamesls opened 8 years ago

jamesls commented 8 years ago

Example:

0.746429 dcli                 describe-reserved-instances-listings
0.298566 dcli                 describe-classic-link-instances

describe-classic-link-instances should be higher.

joguSD commented 7 years ago

I did some testing with this and have something that works but it has edge cases where things that matched before wont match now because it skips the next occurrence for the next occurrence on a boundary.

describe-classic-link-instances
^--^------^---^
1  2      3   4

This completion is currently punished in two ways: 1) It's skipping to characters that aren't at a 'word' boundary (moves 2,3,4). 2) It's not matching most of the completion string (15/31 characters)

Compared to:

describe-reserved-instances-listings
^--^------------------------^^
1  2                        34

Completes 30/36. And the jump from 2 -> 3 isn't penalized very much because 3 is at a boundary. So it basically gets to skip two words and most of the string for nearly free.

Where it's possible for dcli to match like this:

describe-classic-link-instances
^--------^-------^----^
1        2       3    4

In this case you complete more of the word and the moves are to word boundaries (specifically the next word boundary) which isn't penalized as much. We would need to add some prioritization for the next occurrence of the character vs the next occurrence of the character at a boundary or test both and choose the 'better' completion score.