Fuzzy search gives rather wrong results in entity picker

[ildar170975]

After adding a fuzzy search logic into entity picker, it gives lots of wrong results.
Here is an example - other 3 entities have maximum "su" substring:

I can understand intentions of people who asked about adding this fuzzy logic, but the current implementation gives rather wrong results.

[breakthestatic]

This appears correct. As noted in my other comments, the fuzzy search will give the highest rank to the closest match. In this case, sun.sun matches the query sun., and the "closeness" of each of the constituent characters (adjacent) means that it will rank very highly, and therefore appear at the top of the list.

However, fuzzy search essentially matches any results that have the query characters, separated by any number of other characters, as long as they are in order. In this example, it's a bit tough to say what that match is, since the entities are cut-off.

I definitely see "sun" in both searched fields:
entity_id: sensor.iiyama_asus_p8z68_v_pro_nuvoton_nct6776.
name: IIYAMA ASUS P8Z68-V PRO Nuvoton NCT6776F Volta

There are the ellipses for the overflow, but those are purely visual and shouldn't be included in the match. Can you provide the full strings for both the entity_id and name fields? If there's no period/dot in the remainder of either field, then this is actually a bug.

I did try to recreate it locally by using a dummy entity with what I can see of your names/ids. entity_id can't have a ., so that pretty much means the name field is likely where the . could be. When I include a . in the entity name, it does appear in the list, which is correct, since IIYAMA ASUS P8Z68-V PRO Nuvoton NCT6776F Voltage.Test now matches. Conversely, if I remove the . in the entity name, only sun.sun appears, since there's no longer any . after the n match in the string.

[breakthestatic]

Ahh that explains it... the ones that are appearing when you query "sun." do have dots in their names (specifically the three 3.3V ones):

All of the following match fuzzy search because of the dots:

^{IIYAMA A}SU^{S P8Z68-V PRO} N^{uvoton NCT6776F Voltages Analog +3}.^3V

^{IIYAMA A}SU^{S P8Z68-V PRO} N^{uvoton NCT6776F Voltages +3}.^3V

^{IIYAMA A}SU^{S P8Z68-V PRO} N^{uvoton NCT6776F Voltages Standby +3}.^3V

The fuzzy search utility, as implemented by Home Assistant, allows any number of other characters between the matching ones. The only real criteria is that all of the characters in the query string exist, in order in the target. There are other algorithms that take proximity into account in the scoring, but that isn't how the pre-existing filter/sort used by HA is configured.

BTW, not like it helps, but I didn't code the fuzzy search at all. It already existed and was used in other parts of the UI, just not the "picker" components yet. I do agree that some type of closeness setting would be ideal, but @karwosts indicated such a setting would likely not fly with the lead devs. I'd try looking into adding that, but am not very familiar with any of the settings persistence aspects of HA, and given the low likelihood of being merged, would be a somewhat large time-sink. Perhaps someone more well-versed could take a look though?

[karwosts]

I think if someone wanted to go look through the fuzzyScore algorithm a good case for a PR could be made to set the filter threshold at something other than "undefined", someone would just have to do a test with some cases and pick a threshold that seems to return sane choices.

Agree that just having all the characters is pretty weak filter.

[AndreKR]

Winamp had the perfect search decades ago, I don't understand why nowadays this seems to be such a hard problem.

Split the search term at whitespace into parts, then show all items that contain all the parts, anywhere in any of their labels, keeping whatever sort order the items have.