Enhance search algorithm

Description of the new feature/enhancement

When I make a typo and no matches are found with winget search. It would be nice if additional logic might be able to make suggestions.

https://github.com/microsoft/winget-pkgs/pull/14773

Proposed technical implementation details (optional)

The building blocks already exist: the SQLite index supports MatchType::Fuzzy and MatchType::FuzzySubstring (fuzzy is used today for installed-package correlation, not for user search). The default winget search uses MatchType::Substring, so a typo simply returns zero results with no fallback.

Suggested bounded MVP (start here):

• Scope to the search command and the local/SQLite source only.
• When the initial query returns zero matches, re-issue the same query with MatchType::FuzzySubstring and, if candidates come back, present them as suggestions (e.g., "No package found matching ''. Did you mean:") followed by the candidate list.
• Gate the behavior behind a setting (with a sensible default), consistent with how we pair new behaviors with a setting to prefer/require/disable them.

Out of scope for the MVP / follow-up work:

• REST and composite sources - search aggregates across sources and the REST search serializer forwards match types; not every REST source implements fuzzy matching, so the fallback must degrade gracefully per source rather than error. Handle local-source first, then extend.
• Suggestion quality/ranking - the current fuzzy match is n-gram/moniker-based rather than a classic edit-distance "did you mean," so relevance thresholds and ranking will need tuning to avoid noisy suggestions. This is the main risk and likely the bulk of the effort.
• Other commands - the same zero-result path exists for install/upgrade/show (single-query). Whether to surface suggestions there too is a follow-up decision once the search UX is proven.

The local-source search-only slice is small and self-contained; the cross-source behavior and suggestion ranking are the parts that carry the real complexity.

(Updated with GitHub Copilot assistance.)

Start at the search command's zero-result path and inspect the local SQLite source, then compare existing uses of MatchType::Fuzzy and MatchType::FuzzySubstring with the project's patterns for settings. Done means the local-source search can optionally show bounded fuzzy suggestions after zero substring matches, with tests covering the setting and suggestion output.