Skip to main content

FastFzy

The lua implementation of the fzy string matching algorithm. This algorithm is optimized for matching stuff on the terminal, but should serve well as a baseline search algorithm within a game too.

See:

Modified from the initial code to fit this codebase. While this definitely messes with some naming which may have been better, it also keeps usage of this library consistent with other libraries.

Notes:

  • A higher score is better than a lower score
  • Scoring time is O(n*m) where n is the length of the needle and m is the length of the haystack.
  • Scoring memory is also O(n*m)
  • Should do quite well with small lists

This was ported from Quenty's Fzy.

TODO: Support UTF8

Types​

FzyConfiguration​

</>
interface FzyConfiguration {
CapitalMatchScore: number
CaseSensitive: boolean
ConsecutiveMatchScore: number
DotMatchScore: number
GapInnerScore: number
GapLeadingScore: number
GapTrailingScore: number
MaxMatchLength: number
SlashMatchScore: number
WordMatchScore: number
}

Configuration for FastFzy. See FastFzy.CreateConfiguration for details. This affects scoring and how the matching is done.

FilterResult​

</>
interface FilterResult {
Index: number--

The index of the line in haystacks.

Positions: {int}--

The positions of the needle in haystack.

Score: number--

The score returned by FastFzy.Score

String: string--

The line in haystacks.

}

An interface returned by FastFzy.BetterFilter.

Functions​

CreateConfiguration​

</>
FastFzy.CreateConfiguration(maybeConfiguration: table) → FzyConfiguration

Creates a new configuration for Fzy.

IsFzyConfiguration​

</>
FastFzy.IsFzyConfiguration(configuration: any) → boolean

Returns true if it is a FzyConfiguration.

HasMatch​

</>
FastFzy.HasMatch(
configuration: FzyConfiguration,
needle: string,
haystack: string
) → boolean

Check if needle is a subsequence of the haystack.

Usually called before FastFzy.Score or FastFzy.Positions.

IsPerfectMatch​

</>
FastFzy.IsPerfectMatch(
configuration: FzyConfiguration,
needle: string,--

must be a subsequence of haystack, or the result is undefined.

haystack: string
) → boolean

Computes whether a needle or haystack are a perfect match or not

Score​

</>
FastFzy.Score(
configuration: FzyConfiguration,
needle: string,--

must be a subsequence of haystack, or the result is undefined.

haystack: string
) → number--

higher scores indicate better matches. See also FastFzy.GetMinScore and FastFzy.GetMaxScore.

Compute a matching score.

Positions​

</>
FastFzy.Positions(
configuration: FzyConfiguration,
needle: string,--

must be a subsequence of haystack, or the result is undefined.

haystack: string
) → (
{int},--

indices, where indices[n] is the location of the nth character of needle in haystack.

number--

the same matching score returned by score

)

Compute the locations where fzy matches a string.

Determine where each character of the needle is matched to the haystack in the optimal match.

Filter​

</>
FastFzy.Filter(
configuration: FzyConfiguration,
needle: string,
haystacks: {string}
) → {
{
idx,
positions,
score
},
...
}

Apply FastFzy.HasMatch and FastFzy.Positions to an array of haystacks.

Returns an array with one entry per matching line in haystacks, each entry giving the index of the line in haystacks as well as the equivalent to the return value of positions for that line.

Notice

For Luau, I'd recommend using FastFzy.BetterFilter instead, as this specific function doesn't really have the best Luau support.

BetterFilter​

</>
FastFzy.BetterFilter(
configuration: FzyConfiguration,
needle: string,
haystacks: {string}
) → {FilterResult}

An alternative to FastFzy.Filter that returns an array of FastFzy.FilterResult. This is more ideal for Luau at the cost of some speed, as Luau does not support strict arrays the same way that TypeScript would

GetMinScore​

</>
FastFzy.GetMinScore() → number

The lowest value returned by score.

In two special cases:

the FastFzy.Score function will return this exact value, which can be used as a sentinel. This is the lowest possible score.

GetMaxScore​

</>
FastFzy.GetMaxScore() → number

The score returned for exact matches. This is the highest possible score.

GetMaxLength​

</>
FastFzy.GetMaxLength(configuration: FzyConfiguration) → number

The maximum size for which fzy will evaluate scores.

GetScoreFloor​

</>
FastFzy.GetScoreFloor(configuration: FzyConfiguration) → number

The minimum score returned for normal matches.

For matches that don't return FastFzy.GetMinScore, their score will be greater than than this value.

GetScoreCeiling​

</>
FastFzy.GetScoreCeiling(configuration: FzyConfiguration) → number

The maximum score for non-exact matches.

For matches that don't return FastFzy.GetMaxScore, their score will be less than this value.

Show raw api
{
    "functions": [
        {
            "name": "CreateConfiguration",
            "desc": "Creates a new configuration for Fzy.",
            "params": [
                {
                    "name": "maybeConfiguration",
                    "desc": "",
                    "lua_type": "table"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "FzyConfiguration"
                }
            ],
            "function_type": "static",
            "source": {
                "line": 109,
                "path": "src/init.luau"
            }
        },
        {
            "name": "IsFzyConfiguration",
            "desc": "Returns true if it is a [FzyConfiguration].",
            "params": [
                {
                    "name": "configuration",
                    "desc": "",
                    "lua_type": "any"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "boolean"
                }
            ],
            "function_type": "static",
            "source": {
                "line": 140,
                "path": "src/init.luau"
            }
        },
        {
            "name": "HasMatch",
            "desc": "Check if `needle` is a subsequence of the `haystack`.\n\nUsually called before [FastFzy.Score] or [FastFzy.Positions].",
            "params": [
                {
                    "name": "configuration",
                    "desc": "",
                    "lua_type": "FzyConfiguration"
                },
                {
                    "name": "needle",
                    "desc": "",
                    "lua_type": "string"
                },
                {
                    "name": "haystack",
                    "desc": "",
                    "lua_type": "string"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "boolean"
                }
            ],
            "function_type": "static",
            "source": {
                "line": 165,
                "path": "src/init.luau"
            }
        },
        {
            "name": "IsPerfectMatch",
            "desc": "Computes whether a needle or haystack are a perfect match or not",
            "params": [
                {
                    "name": "configuration",
                    "desc": "",
                    "lua_type": "FzyConfiguration"
                },
                {
                    "name": "needle",
                    "desc": "must be a subsequence of `haystack`, or the result is undefined.",
                    "lua_type": "string"
                },
                {
                    "name": "haystack",
                    "desc": "",
                    "lua_type": "string"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "boolean"
                }
            ],
            "function_type": "static",
            "source": {
                "line": 285,
                "path": "src/init.luau"
            }
        },
        {
            "name": "Score",
            "desc": "Compute a matching score.",
            "params": [
                {
                    "name": "configuration",
                    "desc": "",
                    "lua_type": "FzyConfiguration"
                },
                {
                    "name": "needle",
                    "desc": "must be a subsequence of `haystack`, or the result is undefined.",
                    "lua_type": "string"
                },
                {
                    "name": "haystack",
                    "desc": "",
                    "lua_type": "string"
                }
            ],
            "returns": [
                {
                    "desc": "higher scores indicate better matches. See also [FastFzy.GetMinScore] and [FastFzy.GetMaxScore].",
                    "lua_type": "number"
                }
            ],
            "function_type": "static",
            "source": {
                "line": 298,
                "path": "src/init.luau"
            }
        },
        {
            "name": "Positions",
            "desc": "Compute the locations where fzy matches a string.\n\nDetermine where each character of the `needle` is matched to the `haystack`\nin the optimal match.",
            "params": [
                {
                    "name": "configuration",
                    "desc": "",
                    "lua_type": "FzyConfiguration"
                },
                {
                    "name": "needle",
                    "desc": "must be a subsequence of `haystack`, or the result is undefined.",
                    "lua_type": "string"
                },
                {
                    "name": "haystack",
                    "desc": "",
                    "lua_type": "string"
                }
            ],
            "returns": [
                {
                    "desc": "indices, where `indices[n]` is the location of the `n`th character of `needle` in `haystack`.",
                    "lua_type": "{int}"
                },
                {
                    "desc": "the same matching score returned by `score`",
                    "lua_type": "number"
                }
            ],
            "function_type": "static",
            "source": {
                "line": 334,
                "path": "src/init.luau"
            }
        },
        {
            "name": "Filter",
            "desc": "Apply [FastFzy.HasMatch] and [FastFzy.Positions] to an array of haystacks.\n\nReturns an array with one entry per matching line in `haystacks`,\neach entry giving the index of the line in `haystacks` as well as\nthe equivalent to the return value of `positions` for that line.\n\n:::info Notice\nFor Luau, I'd recommend using [FastFzy.BetterFilter] instead, as\nthis specific function doesn't really have the best Luau support.\n:::",
            "params": [
                {
                    "name": "configuration",
                    "desc": "",
                    "lua_type": "FzyConfiguration"
                },
                {
                    "name": "needle",
                    "desc": "",
                    "lua_type": "string"
                },
                {
                    "name": "haystacks",
                    "desc": "",
                    "lua_type": "{string}"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "{{idx, positions, score}, ...}"
                }
            ],
            "function_type": "static",
            "source": {
                "line": 402,
                "path": "src/init.luau"
            }
        },
        {
            "name": "BetterFilter",
            "desc": "An alternative to [FastFzy.Filter] that returns an array of [FastFzy.FilterResult]. This\nis more ideal for Luau at the cost of some speed, as Luau does not support strict arrays\nthe same way that TypeScript would",
            "params": [
                {
                    "name": "configuration",
                    "desc": "",
                    "lua_type": "FzyConfiguration"
                },
                {
                    "name": "needle",
                    "desc": "",
                    "lua_type": "string"
                },
                {
                    "name": "haystacks",
                    "desc": "",
                    "lua_type": "{string}"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "{FilterResult}"
                }
            ],
            "function_type": "static",
            "source": {
                "line": 443,
                "path": "src/init.luau"
            }
        },
        {
            "name": "GetMinScore",
            "desc": "The lowest value returned by `score`.\n\nIn two special cases:\n - an empty `needle`, or\n - a `needle` or `haystack` larger than than [FastFzy.GetMaxLength],\n\nthe [FastFzy.Score] function will return this exact value, which can be used as a\nsentinel. This is the lowest possible score.",
            "params": [],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "number"
                }
            ],
            "function_type": "static",
            "source": {
                "line": 475,
                "path": "src/init.luau"
            }
        },
        {
            "name": "GetMaxScore",
            "desc": "The score returned for exact matches. This is the highest possible score.",
            "params": [],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "number"
                }
            ],
            "function_type": "static",
            "source": {
                "line": 484,
                "path": "src/init.luau"
            }
        },
        {
            "name": "GetMaxLength",
            "desc": "The maximum size for which `fzy` will evaluate scores.",
            "params": [
                {
                    "name": "configuration",
                    "desc": "",
                    "lua_type": "FzyConfiguration"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "number"
                }
            ],
            "function_type": "static",
            "source": {
                "line": 494,
                "path": "src/init.luau"
            }
        },
        {
            "name": "GetScoreFloor",
            "desc": "The minimum score returned for normal matches.\n\nFor matches that don't return [FastFzy.GetMinScore], their score will be greater\nthan than this value.",
            "params": [
                {
                    "name": "configuration",
                    "desc": "",
                    "lua_type": "FzyConfiguration"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "number"
                }
            ],
            "function_type": "static",
            "source": {
                "line": 509,
                "path": "src/init.luau"
            }
        },
        {
            "name": "GetScoreCeiling",
            "desc": "The maximum score for non-exact matches.\n\nFor matches that don't return [FastFzy.GetMaxScore], their score will be less than\nthis value.",
            "params": [
                {
                    "name": "configuration",
                    "desc": "",
                    "lua_type": "FzyConfiguration"
                }
            ],
            "returns": [
                {
                    "desc": "",
                    "lua_type": "number"
                }
            ],
            "function_type": "static",
            "source": {
                "line": 524,
                "path": "src/init.luau"
            }
        }
    ],
    "properties": [],
    "types": [
        {
            "name": "FzyConfiguration",
            "desc": "Configuration for FastFzy. See [FastFzy.CreateConfiguration] for details. This affects scoring\nand how the matching is done.",
            "fields": [
                {
                    "name": "CapitalMatchScore",
                    "lua_type": "number",
                    "desc": ""
                },
                {
                    "name": "CaseSensitive",
                    "lua_type": "boolean",
                    "desc": ""
                },
                {
                    "name": "ConsecutiveMatchScore",
                    "lua_type": "number",
                    "desc": ""
                },
                {
                    "name": "DotMatchScore",
                    "lua_type": "number",
                    "desc": ""
                },
                {
                    "name": "GapInnerScore",
                    "lua_type": "number",
                    "desc": ""
                },
                {
                    "name": "GapLeadingScore",
                    "lua_type": "number",
                    "desc": ""
                },
                {
                    "name": "GapTrailingScore",
                    "lua_type": "number",
                    "desc": ""
                },
                {
                    "name": "MaxMatchLength",
                    "lua_type": "number",
                    "desc": ""
                },
                {
                    "name": "SlashMatchScore",
                    "lua_type": "number",
                    "desc": ""
                },
                {
                    "name": "WordMatchScore",
                    "lua_type": "number",
                    "desc": ""
                }
            ],
            "source": {
                "line": 78,
                "path": "src/init.luau"
            }
        },
        {
            "name": "FilterResult",
            "desc": "An interface returned by [FastFzy.BetterFilter].",
            "fields": [
                {
                    "name": "Index",
                    "lua_type": "number",
                    "desc": "The index of the line in `haystacks`."
                },
                {
                    "name": "Positions",
                    "lua_type": "{int}",
                    "desc": "The positions of the `needle` in `haystack`."
                },
                {
                    "name": "Score",
                    "lua_type": "number",
                    "desc": "The score returned by [FastFzy.Score]"
                },
                {
                    "name": "String",
                    "lua_type": "string",
                    "desc": "The line in `haystacks`."
                }
            ],
            "source": {
                "line": 426,
                "path": "src/init.luau"
            }
        }
    ],
    "name": "FastFzy",
    "desc": "The lua implementation of the fzy string matching algorithm. This algorithm\nis optimized for matching stuff on the terminal, but should serve well as a\nbaseline search algorithm within a game too.\n\nSee:\n* https://github.com/swarn/fzy-lua\n* https://github.com/jhawthorn/fzy/blob/master/ALGORITHM.md\n\nModified from the initial code to fit this codebase. While this\ndefinitely messes with some naming which may have been better, it\nalso keeps usage of this library consistent with other libraries.\n\nNotes:\n* A higher score is better than a lower score\n* Scoring time is `O(n*m)` where `n` is the length of the needle\n  and `m` is the length of the haystack.\n* Scoring memory is also `O(n*m)`\n* Should do quite well with small lists\n\nThis was ported from Quenty's [Fzy](https://github.com/Quenty/NevermoreEngine/blob/main/src/fzy/src/Shared/Fzy.lua).\n\nTODO: Support UTF8",
    "source": {
        "line": 31,
        "path": "src/init.luau"
    }
}