comigor / fuzzy Goto Github PK

View Code? Open in Web Editor NEW

37.0 3.0 20.0 146 KB

Fuzzy search in Dart

License: MIT License

Dart 100.00%

fuzzy's Introduction

Fuzzy

Fuzzy search in Dart.

This project is basically a code conversion, subset of Fuse.js.

Installation

add the following to your pubspec.yaml file:

dependencies:
  fuzzy: <1.0.0

then run:

pub get

or with flutter:

flutter packages get

Usage

import 'package:fuzzy/fuzzy.dart';

void main() {
  final fuse = Fuzzy(['apple', 'banana', 'orange']);

  final result = fuse.search('ran');

  result.map((r) => r.output.first.value).forEach(print);
}

Don't forget to take a look at FuzzyOptions!

fuzzy's People

Contributors

Stargazers

Watchers

fuzzy's Issues

Fuzzy search on custom objects

Hi,

According to the documentation we can only search strings. Can we somehow search on a list of objects that have a string to match against?

Example:

void main() {
  final fuse = Fuzzy([Fruit("orange"), Fruit("banana")]);

  final result = fuse.search('ran', (item) => item.name);
  // second argument returns the string to be searched
  // returns list of Fruit instances that matched
}

class Fruit{
  String name;

  Something(this.name);
}

Doesn't work with data models

fuzzy works great with List<String> but if we provide data models with a toString() method it does not return any results. Screenshot and reproduction below.

import 'package:flutter/cupertino.dart';
import 'package:flutter/material.dart';
import 'package:fuzzy/fuzzy.dart';

class FuzzySearchRoute extends StatefulWidget {
  @override
  _FuzzySearchRouteState createState() => _FuzzySearchRouteState();
}

class _FuzzySearchRouteState extends State<FuzzySearchRoute> {
  String pattern = "";

  @override
  Widget build(BuildContext context) {
    final strings = ["foo", "bar", "baz", "biff"];
    final entries = [for (var e in strings) Entry(e)];

    final fuzzyString = Fuzzy(strings).search(pattern);
    final fuzzyEntry = Fuzzy(entries).search(pattern);

    return Scaffold(
      appBar: AppBar(
        title: Text("/fuzzy-search"),
      ),
      body: Align(
        alignment: Alignment.topCenter,
        child: Column(
          mainAxisAlignment: MainAxisAlignment.center,
          mainAxisSize: MainAxisSize.min,
          children: <Widget>[
            SizedBox(height: 16),
            Text("Entries"),
            for (var e in entries) Text(e.value),

            /// String
            SizedBox(height: 16),
            Text("Results (String)"),
            for (var e in fuzzyString) Text(e.item),

            /// Entry
            SizedBox(height: 16),
            Text("Results (Entry)"),
            for (var e in fuzzyEntry) Text(e.item.value),
          ],
        ),
      ),
      bottomNavigationBar: SafeArea(
        child: Padding(
          padding: EdgeInsets.all(16),
          child: CupertinoTextField(
            onChanged: (e) => setState(() => pattern = e),
          ),
        ),
      ),
    );
  }
}

class Entry {
  /// An example data model with searchable toString() method
  Entry(this.value);

  /// The underlying value to search
  final String value;

  /// Fuzzy searchable string
  @override
  String toString() => "$value";
}

searches always return arrayIndex = -1

Tried the example code and many more options, but all the resulted matches have always the arrayIndex equal to -1.

ResultDetails from search Result always have arrayIndex = -1

All search results seem to return ResultDetails.arrayIndex = -1. Indeed, looking at fuzzy.dart, it seems there's some sort of mistake in the parameters of the method _analyze: there is a named parameter int arrayIndex = -1 and int index. When _analyze is called, only index is specified. Throughout the body of _analyze, index is used as the source of that search result index. But when the raw result list is updated, arrayIndex is passed to the ResultDetails constructor.

It seems fixing this is just removing the parameters arrayIndex and replacing its uses with index.

Fails if the pattern is of length 0

The problematic line is here.

final mask = 1 << (patternLen <= 31 ? patternLen - 1 : 30);

If patternLen = 0 then (patternLen <= 31 ? patternLen - 1 : 30)=-1 which promptly fails the shift.

Matches don't seem right

If I have a list:

Maine, Nevada, Tennessee and I type maine, the other two are returned before Maine even though it's an exact match. It's not a sorting issue, this is just a trite example. What am I doing wrong?

Example does not work

import 'package:fuzzy/fuzzy.dart';

void main() {
  final fuse = Fuzzy(['apple', 'banana', 'orange']);

  final result = fuse.search('ran');

  result.map((r) => r.output.first.value).forEach(print);
  //                  ^^^^^^ The getter 'output' isn't defined for the type 'Result<String>'
}

Should probably be r.matches instead

Search crashes when tokenize = true and the query ends with a space

Title says it all :) Here's an example test code:

import 'package:test/test.dart';
import 'package:fuzzy/fuzzy.dart';

void main() {
  test('Search works when tokenize = true and query ends with space', () {
    final fuse = Fuzzy(['apple juice'], options: FuzzyOptions(tokenize: true));
    expect(() => fuse.search('apple'), returnsNormally);
    expect(() => fuse.search('apple j'), returnsNormally);
    expect(() => fuse.search('apple '), returnsNormally);
  });
}

The first two expects succeed, but the last one fails with:

Expected: return normally
  Actual: <Closure: () => List<Result<dynamic>>>
   Which: threw ArgumentError:<Invalid argument(s): -1>

Here's the full stack trace from the test (i.e., removing the expectation):

dart:core                                    int.<<
package:fuzzy/bitap/bitap_search.dart 62:18  bitapSearch
package:fuzzy/bitap/bitap.dart 63:12         Bitap.search
package:fuzzy/fuzzy.dart 175:51              Fuzzy._analyze
package:fuzzy/fuzzy.dart 93:9                Fuzzy._search
package:fuzzy/fuzzy.dart 50:9                Fuzzy.search
test\test.dart 9:10                          main.<fn>

Invalid argument(s): -1

Matching numbers in an expected order

Given a list of items:

id: 2
name: Aroostook Farmland

id: 22
name: Penobscot Bay

id: 29
name: Coastal Islands

I want to be able to type Penob and get a sorting with 22: Penobscot Bay item on top. This currently works.

I also want to be able to type 29 and get a sorting with 29: Coastal Islands item on top.

However, in my current implementation if I type 29 I get 2: Aroostook Farmland on top.

I can't seem to make the search results to have 29 match 29 better than 2.

I was expecting to be able to have search options on each weighted key, since the needs of matching 26 => 26 is different than the needs of matching penob to penobscot.

Any suggestions?

Fuzzy(
  WmdConstants.districts,
  options: FuzzyOptions(
    keys: [
      /// WMD id, ie `23`
      WeightedKey<WmdModel>(
        name: 'id',
        weight: 1.0,
        getter: (e) => e.id.toString(),
      ),

      /// WMD name, ie `Penobscot Bay Area`
      WeightedKey<WmdModel>(
        name: 'name',
        weight: 0.1,
        getter: (e) => e.name.toString(),
      ),
    ],
  ),
);

FormatException on long string+special character

I get a FormatExceptions when user types a special character (e.g. a parenthesis) after a long string.

With test1 test2 test3 test4 test5 ( it works but with test1 test2 test3 test4 test5 test6 ( I get the exception.

Range error when using limit argument to fuse.search

To avoid this error

RangeError (end): Invalid value: Not in inclusive range 0..1: 15

When the exception was thrown, this was the stack:
#0      RangeError.checkValidRange (dart:core/errors.dart:356:9)
#1      List.sublist (dart:core-patch/growable_array.dart:84:38)
#2      Fuzzy.search (package:fuzzy/fuzzy.dart:58:40)
#3      MyFilterSearch.search (package:EveIndy/search.dart:17:25)
#4      _SearchBarState.build.<anonymous closure> (package:EveIndy/gui/widgets/search_bar.dart:40:18)
#5      EditableTextState._formatAndSetValue (package:flutter/src/widgets/editable_text.dart:2630:27)
#6      EditableTextState.updateEditingValue (package:flutter/src/widgets/editable_text.dart:1967:7)
#7      TextInput._handleTextInputInvocation (package:flutter/src/services/text_input.dart:1730:37)
#8      MethodChannel._handleAsMethodCall (package:flutter/src/services/platform_channel.dart:404:55)
#9      MethodChannel.setMethodCallHandler.<anonymous closure>
(package:flutter/src/services/platform_channel.dart:397:34)
#10     _DefaultBinaryMessenger.setMessageHandler.<anonymous closure> (package:flutter/src/services/binding.dart:380:35)
#11     _DefaultBinaryMessenger.setMessageHandler.<anonymous closure> (package:flutter/src/services/binding.dart:377:46)
#12     _invoke2.<anonymous closure> (dart:ui/hooks.dart:190:15)
#16     _invoke2 (dart:ui/hooks.dart:189:10)
#17     _ChannelCallbackRecord.invoke (dart:ui/channel_buffers.dart:42:5)
#18     _Channel.push (dart:ui/channel_buffers.dart:132:31)
#19     ChannelBuffers.push (dart:ui/channel_buffers.dart:329:17)
#20     PlatformDispatcher._dispatchPlatformMessage (dart:ui/platform_dispatcher.dart:589:22)
#21     _dispatchPlatformMessage (dart:ui/hooks.dart:89:31)
(elided 3 frames from dart:async)

This line

fuzzy/lib/fuzzy.dart

Line 58 in f4135f6

if (limit > 0) {

should be changed to

if (limit > 0 && resultsAndWeights.results.length > limit) {

WeightedKey should contain an assertion that weight is not null

The constructor should also use @required for required arguments, as a hint to analysis.

Result score with tokenize = true ignores token score average

I was debugging some searches with tokenize = true and noticed that the search result score didn't seem to consider the token score average, only the mainSearchResult.score (i.e. the full text score). According to the code, it seems that, when there is a token score average, the final result score should be the average of full text score / token score:

156    var averageScore = -1;
...
...       [code that computes averageScore]
...
199    var finalScore = mainSearchResult.score;
200    if (averageScore > -1) {
201      finalScore = (finalScore + averageScore) / 2;
202    }

The problem is that the code that computes averageScore is inside a scope which declares a new averageScore variable, then the original variable never gets updated

162    if (options.tokenize) {
...
...         [code that searches through tokens]
...
193      final averageScore =    <<<<< this shouldn't be a declaration
194          scores.fold(0, (memo, score) => memo + score) / scores.length;
195
196      _log('Token score average: $averageScore');
197    }
198
199    var finalScore = mainSearchResult.score;
200    if (averageScore > -1) {
201      finalScore = (finalScore + averageScore) / 2;
202    }

Search results don't hone, they fluctuate

This may be a configuration issue as I have no experience with fuzzy searching, opting into services like Algolia. However, I need an offline search-as-you-type feature and I'm looking for a similar experience.

Behavior: as you add characters the results alternate between a single result (sometimes missing expected results) and a bunch of seemingly unrelated results.

An example of missing results is typing penobscot and not getting back Mid-Penobscot River Valley or North Penobscot Farm-Woodlands

Expected: as you type more characters the results get more and more honed.

static final _districtFuse = Fuzzy(
  WmdConstants.districts,
  options: FuzzyOptions(
    keys: [
      /// WMD id, ie `23`
      WeightedKey<WmdModel>(
        name: 'id',
        weight: 1.0,
        getter: (e) => e.id.toString(),
      ),

      /// WMD name, ie `Penobscot Bay Area`
      WeightedKey<WmdModel>(
        name: 'name',
        weight: 0.1,
        getter: (e) => e.name.toString(),
      ),
    ],
  ),
);

final dataSet = {
  1: "Upper St. John River Valley",
  2: "Clayton Lake to St. Francis",
  3: "North Aroostook Farmland",
  4: "Chesuncook Lake to Daaquam",
  5: "Matagamon to Big Machias River",
  6: "Aroostook Farmland",
  7: "Rangeley Area",
  8: "Eustis to Jackman Area",
  9: "East of Moosehead Lake",
  10: "Foothills East of Baxter Park",
  11: "North Penobscot Farm-Woodlands",
  12: "Upper Androscoggin Valley",
  13: "Franklin and Somerset Co. Areas",
  14: "South and East of Moosehead Lake",
  15: "Oxford County Foothills",
  16: "Belgrade Lakes Area",
  17: "North-Central Farm-Woodlands",
  18: "Mid-Penobscot River Valley",
  19: "North of the Airline",
  20: "York County",
  21: "Cumberland County",
  22: "Kennebec River Valley",
  23: "South-Central Farm-Woodlands",
  24: "South Coastal Strip",
  25: "Mid-Coastal Strip",
  26: "Penobscot Bay Area",
  27: "Eastern Coastal Plain",
  28: "South of the Airline",
  29: "Maine’s Coastal Islands",
};

Results randomly change?

Super strange behaviour, Meagher street should stay but it disappears when the street is added

Kapture.2024-02-09.at.21.50.08.mp4

  void updateSearched(String searchTerm) {
    _searched.clear();
    if (searchTerm.isEmpty) {
      setState(() {
        _searched = List.from(_clinics);
      });
    }
    if (searchTerm.isNotEmpty) {
      for (var clinic in _clinics) {

        String clinicName = clinic['clinic']['name'].toLowerCase();
        String clinicAddress = clinic['clinic']['address'].toLowerCase();
        String clinicSpeciality = clinic['clinic']['speciality'].toLowerCase();
        String clinicSuburb = clinic['clinic']['suburb'].toLowerCase();
        Fuzzy fuzzy = Fuzzy([clinicName, clinicAddress, clinicSpeciality, clinicSuburb]);

        List<Result<dynamic>> results = fuzzy.search(searchTerm.toLowerCase());

        if (results.isNotEmpty) {
          List<dynamic> matchedStrings = results.map((result) => result.item).toList();
          print(matchedStrings);
          print(searchTerm);

          if (matchedStrings.length > 0) {
            _searched.add(clinic);
            break;
          }
        }
  }

Inconsistant search result

Hi,

I have a small set of strings to search:

first_name_6 last_name_6
first_name_2 last_name_2
first_name_1 last_name_1
first_name_5 last_name_5
first_name_4 last_name_4
first_name_3 last_name_3

(it's a single string field).

Searching with different parameters yields inconsistent results:

6 =>
first_name_6 last_name_6

_6 =>
first_name_6 last_name_6

name_6 =>
first_name_6 last_name_6
first_name_2 last_name_2
first_name_1 last_name_1
first_name_5 last_name_5
first_name_4 last_name_4
first_name_3 last_name_3

This last search should result in only the first line... Any hint? Seems to be linked to the presence of an '_' in the strings.

BTW my configuration:

_fuse = Fuzzy<model.TribeMember>(
      _members,
      options: FuzzyOptions(
        findAllMatches: true,
        keys: [
          WeightedKey(name: "fullName", getter: (i) => i.fullName, weight: 1.0)
        ],
        threshold: 0.4,
        isCaseSensitive: false,
      ),
    );

Variable number of WeightedKeys from List

I have an object that has a default name (String) and a list of aliases (List<String>). Right now I just have a WeightedKey of the name, but I'd also like to search in the aliases. The list of aliases is of variable length. Is there a simple way to do this?

Score not showing properly

First of all, amazing library. But, I guess the score property of result object is always zero (even when it hasn't found any matches).

Example:

void testFuzzy() {
    final fuse = Fuzzy(
      [
        Person('John', 'Doe', 29),
        Person('Jane', 'Doe', 32),
        Person('Peter', 'Parker', 36),
        Person('Bruce', 'Wayne', 30),
        Person('Clark', 'Kent', 50),
        Person('Tony', 'Stark', 34),
        Person('Clint', 'Barton', 35),
      ],
      options: FuzzyOptions(
        keys: [WeightedKey<Person>(name: 'firstname', getter: (p) => p.firstname, weight: 1)],
        shouldNormalize: true,
        isCaseSensitive: false,
        shouldSort: false,
        findAllMatches: false,
        verbose: true,
      ),
    );

    var result = fuse.search('John');

    if (result.isNotEmpty) {
      result
          .forEach((r) => print('${r.item.firstname} ${r.item.surname} (${r.item.age}) | score: ${r.score}'));
    } else {
      print('no results');
    }
  }


class Person {
  final String firstname;
  final String surname;
  final int age;

  Person(this.firstname, this.surname, this.age);
}

output shows:

flutter: Full text: "John", score: 0.0
flutter: Score average (final): 0.0
flutter:
Check Matches: true
flutter: Full text: "Jane", score: 0.5
flutter: Score average (final): 0.5
flutter:
Check Matches: true
flutter: Full text: "Peter", score: 1.0
flutter: Score average (final): 1.0
flutter:
Check Matches: true
flutter: Full text: "Bruce", score: 1.0
flutter: Score average (final): 1.0
flutter:
Check Matches: true
flutter: Full text: "Clark", score: 1.0
flutter: Score average (final): 1.0
flutter:
Check Matches: true
flutter: Full text: "Tony", score: 0.5
flutter: Score average (final): 0.5
flutter:
Check Matches: true
flutter: Full text: "Clint", score: 1.0
flutter: Score average (final): 1.0
flutter:
Check Matches: true
flutter:
Computing score:
flutter: John Doe (29) | score: 0.0
flutter: Jane Doe (32) | score: 0.0
flutter: Tony Stark (34) | score: 0.0

We can see that on verbose output the score is taken correctly, but when printing after search, is aways zero.

I can workaround it doing:

    result.forEach((r) => r.score = r.matches[0].score);
    result.sort((a,b) => a.score.compareTo(b.score));

But I'm not happy with this approach, is there a solution for this? Or perhaps I'm doing something wrong, please help.
Thanks in advance

Release null safe version

I checked and all of your dependencies except latinize have released a null safe version. I have opened an issue on latinize's end: lucasmafra/latinize#3. Once they release it, could you release a null safe version? Thanks.

Sorry if that was already your plan, then this issue can serve for tracking progress.