Ruby十万级哈希数组的快速模糊搜索实现问询

Hey there! When dealing with fuzzy search on 100k+ hash entries, you don’t have to settle for slow full-array scans. Let’s walk through practical, fast solutions tailored to your Ruby scenario:

1. Precompile a Name Index + Regex Grep (Simple & Balanced) #

The first win is to decouple the names from the full hash entries—working with a smaller, dedicated list of names will speed up searches significantly. We’ll also precompile our regex to avoid redundant work on each search.

# Do this ONCE when your data loads (not every search!)
@name_to_entry = @t.to_h { |entry| [entry["nm"], entry] }
@all_names = @name_to_entry.keys

def fuzzy_search(query)
  # Escape special regex characters and make the search case-insensitive
  regex = /#{Regexp.escape(query)}/i
  # Grep matches from the name array, then map back to full entries
  @all_names.grep(regex).map { |name| @name_to_entry[name] }
end

# Example usage
fuzzy_search("Mosc") # Returns the Moscow entry
fuzzy_search("raz") # Returns the Razvilka entry (case-insensitive!)

This approach is way faster than scanning the full @t array every time—Ruby’s grep is optimized for array operations, and the index only needs building once.

2. Trie Data Structure (Ultra-Fast Prefix Searches) #

If your fuzzy searches are mostly prefix-based (e.g., typing "Mosc" to find "Moscow"), a Trie tree is unbeatable. Search time depends only on the length of your query, not the size of your dataset.

Here’s a simple Ruby implementation:

class TrieNode
  attr_accessor :children, :entries

  def initialize
    @children = Hash.new { |h, k| h[k] = TrieNode.new }
    @entries = []
  end
end

class Trie
  def initialize(entries)
    @root = TrieNode.new
    entries.each do |entry|
      node = @root
      # Use downcase to support case-insensitive prefix searches
      entry["nm"].downcase.each_char do |char|
        node = node.children[char]
        node.entries << entry
      end
    end
  end

  def search_prefix(prefix)
    node = @root
    prefix.downcase.each_char do |char|
      node = node.children[char]
      return [] unless node # No matches for this prefix
    end
    node.entries.uniq # Avoid duplicate entries from nested nodes
  end
end

# Build the Trie ONCE during initialization
@trie = Trie.new(@t)

# Example usage
@trie.search_prefix("mosc") # Returns the Moscow entry
@trie.search_prefix("fir") # Returns the Firozpur Jhirka entry

This is perfect for autocomplete-style searches where users type from the start of the name.

3. Inverted Index for Arbitrary Substring Searches #

If you need to match substrings anywhere in the name (e.g., searching "ow" to find "Moscow"), an inverted index maps common substrings to their entries. We’ll limit substring length to balance memory usage and search accuracy.

# Build the inverted index ONCE
MIN_SUBSTRING_LENGTH = 3 # Adjust based on your needs
@inverted_index = Hash.new { |h, k| h[k] = [] }

@t.each do |entry|
  name = entry["nm"].downcase
  # Generate all valid substrings from the name
  (0..name.length - MIN_SUBSTRING_LENGTH).each do |i|
    substring = name[i, MIN_SUBSTRING_LENGTH]
    @inverted_index[substring] << entry unless @inverted_index[substring].include?(entry)
  end
end

def fuzzy_substring_search(query)
  return [] if query.length < MIN_SUBSTRING_LENGTH
  
  query = query.downcase
  # Get candidate entries from the index, then filter for exact substring matches
  candidates = @inverted_index[query[0, MIN_SUBSTRING_LENGTH]] || []
  candidates.select { |entry| entry["nm"].downcase.include?(query) }
end

# Example usage
fuzzy_substring_search("osc") # Returns the Moscow entry
fuzzy_substring_search("hir") # Returns the Firozpur Jhirka entry

This avoids scanning the entire 100k array every time—we first narrow down candidates via the index, then do a final filter for precision.

4. Simple select with Precompiled Regex (Quick & Dirty, Not Ideal for Large Data) #

If you want the simplest code and don’t need ultra-fast repeated searches, you can use select with a precompiled regex. But note: this scans the full array every time, so it’ll be slower for 100k entries.

def simple_fuzzy_search(query)
  regex = /#{Regexp.escape(query)}/i
  @t.select { |entry| entry["nm"] =~ regex }
end

Only use this if your search volume is low or you don’t want to maintain an index.

Quick Recap #

• Prefix searches? Go with the Trie—blazing fast.
• Arbitrary substring searches? Use the name index + grep or inverted index.
• Simple, one-off searches? The basic select works, but isn’t ideal for large datasets.

内容的提问来源于stack exchange，提问作者arjun