A Simple, Smart Search Algorithm for iOS in Swift

Introduction

This article describes a simple, smart search algorithm that I have used in several iOS apps. The algorithm is smarter than a trivial substring match but not as complex as something like Xcode’s fuzzy matching of method names. It doesn’t understand English or alternate word forms. It’s smart, but simple!

Sample Project

The simplest way to describe the features of the algorithm and see it in use is with a sample project. You can download SmartSearchExample from GitHub and should be able to run it in the iOS simulator without changes. You will need to configure your development team in the app target’s “Signing & Capabilities” tab in order to run it on a real device.

SmartSearchExample sample app for browsing SF Symbols on iOS 14

The Algorithm

At its heart, the algorithm works by matching word prefixes. It can be used when the data to be search is structured as a list of words. I prefer to use the slightly more abstract term “tokens” instead of “words”: groups of characters separated by whitespace.

Use Cases

  • A search for the empty string should match all symbols. Requirement 1: search strings with no tokens match everything.
  • A search for “he” should match symbol names which contain a token that begins with “he” (e.g. heart and bolt.heart.fill). A match should not occur for a symbol that only has the two letters “he” somewhere within a token (e.g. checkmark or rectangle.dashed). Requirement 2: matches only occur on token prefixes.
  • A search for “x bin” should matchxmark.bin, xmark.bin.circle, xmark.bin.circle.fill, and xmark.bin.fill. The matches should not be a union of the matches of separate searches for “x” and “bin”. Requirement 3: each token in the search string must match a token in the data.
  • A search for “up up” should only match symbol names which have two (or more) tokens beginning with “up”. Requirement 4: each token in the search string must match a separate token in the data.
  • A search for “fill circle sq” should match circle.fill.square.fill, square.circle.fill, and square.fill.on.circle.fill. Requirement 5: the order of the tokens in the search string and data do not need to be the same.
  • A search for “p pe” should match (among others) person.badge.plus. In this example, the “p” could be considered to match either person or plus, but “pe” can only match person. The more restrictive (i.e. longer) search token “pe” must match person, allowing "p" to match plus. In combination with requirement 4 (each search token matches a separate data token), this avoids giving different results depending upon the order of tokens in the strings. This is important and subtle behaviour but is actually easy to implement. Requirement 6: longer search tokens should be matched first.
  • Requirement 7: leading and/or trailing spaces in the search string should be ignored.
  • Requirement 8: multiple spaces between tokens in the search string should be treated as a single space; they do not create zero length search tokens.

Pseudocode

Using the algorithm will require a matcher object to be initialised with the search text. That object will have a method which takes a candidate string as a parameter (the data item to test for a match, a space-separated SF Symbol name in the sample app). The method returns a boolean value indicating whether the candidate string matched the search text or not. In the sample project the SF symbol names (with periods replaced by spaces) are searched each time the search bar contents changes. Those that match are shown on screen:

Pseudocode for using the search algorithm
Pseudocode for the matching algorithm

Real Swift Code

I don’t want to spend much time in this article discussing the sample project itself. I want to focus on how to use the searching algorithm and how matching is implemented. The app has an array of SFSymbolName structs that defines the list of all the symbol names. A list style collection view shows rows with the image and name of matching symbols (or all symbols if a search is not being performed).

Slightly simplified code from the sample app to search through all the SF Symbol names to find matches
SmartSearchMatcher’s public API
SmartSearchMatcher’s matches method

Real World Considerations

The data being searched needs to be in an appropriate form for the algorithm to be useful: whitespace-delimited tokens. I’ve used this algorithm in several of my own apps: Easy Shopping List, Easy Cooking Timer, Meeting Cost Timers and Adaptivity. The first three search over user-created names (shopping list items, meal names, meeting template names). Adaptivity is more interesting and I will discuss it in more detail below.

Search Text and Data Formats

The sample app demonstrates a simple conversion of actual SF Symbol names to tokens by replacing each period with a space. But what if the user’s search text contains a period? As presented above, the code in updateSearchResults would not match anything because there are no periods in the candidate strings passed to the matches method. That’s not a good experience. If I literally search for “xmark.bin” I would expect to see xmark.bin, xmark.bin.circle, xmark.bin.circle.fill, and xmark.bin.fill.

More complex version of using SmartSearchMatcher in the sample app to better handle searches containing periods

Adaptivity Search Examples

Amongst the many features of my app Adaptivity are views for browsing System Colors and System Images.

Adaptivity’s System Colors view matches color name tokens and full name prefixes
Adaptivity’s System Images view matches deprecated symbol names and words within tokens

Possible Improvements

The algorithm is smart, but simple. Here’s a few possible optimisations that could be worth implementing:

  • If candidate strings have lots of tokens, the inner loop my be more efficient if it iterated over a set of tokens as opposed to an array. Depending on how many matching tokens there are, the cost of removing each matching token from an array might be more than the overhead of building the set (which has O(1) time complexity for removal).
  • If the search token does not match the very beginning of the candidate token, we don’t care if it matches later. Using range:of:options: to search for a match and then, if a match is found, testing if was at the start of the candidate token will needlessly search the whole string. A smarter way of matching only the candidate token prefix could save a little time. If we didn’t care about case insensitivity or accented characters, we could use starts:with:. In my apps, I do care!
  • A meta-optimisation would be to take advantage of the fact that some types of change to the search text cannot possibly match any items that a previous search had already failed to match. For example, adding a character to the end of a search token, or adding a new search token, will match either the same or fewer results as before. It is wasted effort to test any data items that didn’t match a less restrictive search text. The matches from a previous search could be used as a smaller data set for a subsequent search if this could be detected.
  • Search results could be cached if it is likely the user would repeat a previous search (e.g. when removing a character from the end of a search token, changing back to a previously-used search text).
  • If the number of items to search is large, or the user could be expected to quickly type relatively long search text, delaying the search until the search text had remain unchanged for a fraction of a second could avoid making searches which are immediately obsolete because the search text has changed. This kind of optimisation is common when searching requires performing a (relatively) slow network request to look for matches.

Conclusion

The searching within an app can be made more useful and powerful by treating the search text and underlying data as a series of tokens and filtering based on matching token prefixes. As seen in the sample and Adaptivity’s System Colors and System Images views, more complex representations of the underlying data can allow for even smarter matching. The algorithm remains the same, but multiple representations of each item in the data set (system color or system image) is checked for matches.

Other Articles That You Might Like

I have written about the changes made to SF Symbols in different iOS versions: SF Symbols Changes in iOS 14 and SF Symbols Changes in iOS 14.2.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Geoff Hackworth

Independent and freelance software developer for iPhone, iPad and Mac