Pure Front-End Inverted Full-Text Search

Original Link: https://i18n.site/blog/tech/search

Sequence

After several weeks of development, i18n.site (a purely static markdown multilingual translation & website building tool) now supports pure front-end full-text search.

This article will share the technical implementation of i18n.site's pure front-end full-text search. Visit i18n.site to experience the search functionality.

Code is open-source: Search kernel / Interactive interface

An Overview of Serverless Full-Text Search Solutions

For small and medium-sized purely static websites such as documents/personal blogs, building a self-built full-text search backend is too heavy, and service-free full-text search is the more common choice.

Serverless full-text search solutions are divided into two main categories:

The first involves third-party search service providers like algolia.com that offer front-end components for full-text search.

Such services require payment based on search volume and are often unavailable to users in mainland China due to compliance issues.

They cannot be used offline or on intranets, and have significant limitations. This article will not elaborate further.

The second category is pure front-end full-text search.

Currently, common pure front-end full-text search tools include lunrjs and ElasticLunr.js (a secondary development based on lunrjs).

lunrjs has two methods for building indexes, both with their own issues.

1. Pre-built index files

Because the index includes all the words from the documents, it is large in size.
Every time a document is added or modified, a new index file must be loaded.
This increases user waiting time and consumes a significant amount of bandwidth.

1. Loading documents and building indexes on the fly

Building an index is a computationally intensive task, and rebuilding it with each access can cause noticeable delays, leading to a poor user experience.

---

In addition to lunrjs, there are other full-text search solutions, such as:

fusejs, which searches by calculating the similarity between strings.

This solution has poor performance and is not suitable for full-text search (refer to Fuse.js Long query takes over 10 seconds, how to optimize?).

TinySearch, which uses a Bloom filter for searching, cannot perform prefix searches (e.g., entering goo to search for good or google) and cannot achieve an autocomplete effect.

Due to the drawbacks of existing solutions, i18n.site has developed a new pure front-end full-text search solution with the following features:

1. Supports multi-language search, with a compact size; the search kernel, when packaged with gzip, is only 6.9KB (in comparison, lunrjs is 25KB)
2. Builds an inverted index based on IndexedDB, with low memory usage and fast performance
3. When documents are added/modified, only the added or modified documents are re-indexed, reducing the amount of calculations
4. Supports prefix search, allowing real-time display of search results as the user types
5. Offline Availability

Details of the i18n.site technical implementation will be introduced below.

Multilingual Word Segmentation

Word segmentation uses the browser's native Intl.Segmenter, which is supported by all mainstream browsers.

The coffeescript code for word segmentation is as follows:

SEG = new Intl.Segmenter 0, granularity: "word"

seg = (txt) =>
  r = []
  for {segment} from SEG.segment(txt)
    for i from segment.split('.')
      i = i.trim()
      if i and !'|`'.includes(i) and !/\p{P}/u.test(i)
        r.push i
  r

export default seg

export segqy = (q) =>
  seg q.toLocaleLowerCase()

Where:

• /p{P}/ is a regular expression that matches punctuation marks, including: ! " # $ % & ' ( ) * , - . / : ; ? @ [ ] ^ _ { | } ~. .
  • split('.')is becauseFirefoxbrowser word segmentation does not segment.` .

  Index Construction

  Five object storage tables are created in IndexedDB:

  • word: id - word
  • doc: id - document URL - document version number
  • docWord: document id - array of word ids
  • prefix: prefix - array of word ids
  • rindex: word id - document id - array of line numbers

  By passing in an array of document url and version number ver, the doc table is checked for the document's existence. If it does not exist, an inverted index is created. Simultaneously, the inverted index for documents not passed in is removed.

  This method allows for incremental indexing, reducing the computational load.

  In the front-end interface, a progress bar for index loading can be displayed to avoid lag during the initial load. See "Animated Progress Bar, Based on a Single progress + Pure CSS Implementation" English / Chinese.

  IndexedDB High Concurrent Writing

  The project is developed based on the asynchronous encapsulation of IndexedDB, idb.

  IndexedDB reads and writes are asynchronous. When creating an index, documents are loaded concurrently to build the index.

  To avoid data loss due to concurrent writes, you can refer to the following coffeescript code, which adds a ing cache between reading and writing to intercept competitive writes.

  `coffee
  pusher = =>
  ing = new Map()
  (table, id, val)=>
  id_set = ing.get(id)
  if id_set
  id_set.add val
  return

  id_set = new Set([val])
  ing.set id, id_set
  pre = await table.get(id)
  li = pre?.li or []
  
  loop
    to_add = [...id_set]
    li.push(...to_add)
    await table.put({id,li})
    for i from to_add
      id_set.delete i
    if not id_set.size
      ing.delete id
      break
  return
  

  rindexPush = pusher()
  prefixPush = pusher()
  `

  Prefix Real-Time Search

  To display search results in real-time as the user types, for example, showing words like words and work that start with wor when wor is entered.

  

  The search kernel uses the prefix table for the last word after segmentation to find all words with that prefix and search sequentially.

  An anti-shake function, debounce (implemented as follows), is used in the front-end interaction to reduce the frequency of searches triggered by user input, thus minimizing computational load.

  js
  export default (wait, func) => {
  var timeout;
  return function(...args) {
  clearTimeout(timeout);
  timeout = setTimeout(func.bind(this, ...args), wait);
  };
  }
  

  Precision and Recall

  The search first segments the keywords entered by the user.

  Assuming there are N words after segmentation, the results are first returned with all keywords, followed by results with N-1, N-2, ..., 1 keywords.

  The search results displayed first ensure query precision, while subsequent loaded results (click the "Load More" button) ensure recall.

  

  On-Demand Loading

  To improve response speed, the search uses the yield generator to implement on-demand loading, returning results after each limit query.

  Note that after each yield, a new IndexedDB query transaction must be opened for the next search.

  Prefix Real-Time Search

  To display search results in real-time as the user types, for example, showing words like words and work that start with wor when wor is entered.

  

  The search kernel uses the prefix table for the last word after segmentation to find all words with that prefix and search sequentially.

  An anti-shake function, debounce (implemented as follows), is used in the front-end interaction to reduce the frequency of searches triggered by user input, thus minimizing computational load.

  js
  export default (wait, func) => {
  var timeout;
  return function(...args) {
  clearTimeout(timeout);
  timeout = setTimeout(func.bind(this, ...args), wait);
  };
  }
  

  Offline Availability

  The index table does not store the original text, only words, reducing storage space.

  Highlighting search results requires reloading the original text, and using service worker can avoid repeated network requests.

  Also, because service worker caches all articles, once a search is performed, the entire website, including search functionality, becomes offline available.

  Optimization for Displaying MarkDown Documents

  The pure front-end search solution provided by i18n.site is optimized for MarkDown documents.

  When displaying search results, the chapter name is shown, and clicking navigates to that chapter.

  

  Summary

  The pure front-end implementation of inverted full-text search, without the need for a server, is very suitable for small to medium-sized websites such as documents and personal blogs.

  i18n.site's open-source self-developed pure front-end search is compact, responsive, and addresses the various shortcomings of current pure front-end full-text search solutions, providing a better user experience.

The above is the detailed content of Pure Front-End Inverted Full-Text Search. For more information, please follow other related articles on the PHP Chinese website!