Class: Zxcvbn::Trie

Inherits:
Object
  • Object
show all
Defined in:
lib/zxcvbn/trie.rb

Overview

A trie (prefix tree) data structure for efficient dictionary matching. Provides fast prefix-based lookups to eliminate unnecessary substring checks.

See Also:

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Trie

Returns a new instance of Trie.



9
10
11
 
# File 'lib/zxcvbn/trie.rb', line 9

def initialize
  @root = {}
end

Instance Method Details

#insert(word, rank) ⇒ Object

Insert a word and its rank into the trie

Parameters:

  • word (String) —

    the word to insert

  • rank (Integer) —

    the rank/frequency of the word



16
17
18
19
20
21
22
23
 
# File 'lib/zxcvbn/trie.rb', line 16

def insert(word, rank)
  node = @root
  word.each_char do |char|
    node[char] ||= {}
    node = node[char]
  end
  node[:rank] = rank
end

#search_prefixes(text, start_pos) ⇒ Array<Array>

Search for all words in the text starting from a given position

Parameters:

  • text (String) —

    the text to search in

  • start_pos (Integer) —

    the starting position

Returns:

  • (Array<Array>) —

    array of [word, rank, start, end] tuples



29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
# File 'lib/zxcvbn/trie.rb', line 29

def search_prefixes(text, start_pos)
  results = []
  node = @root

  (start_pos...text.length).each do |i|
    char = text[i]
    break unless node[char]

    node = node[char]
    results << [text[start_pos..i], node[:rank], start_pos, i] if node[:rank]
  end

  results
end