Class: Zxcvbn::Trie Private

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

Overview

This class is part of a private API. You should avoid using this class if possible, as it may be removed or be changed in the future.

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

See Also:

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Trie

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Returns a new instance of Trie.



19
20
21
 
# File 'lib/zxcvbn/trie.rb', line 19

def initialize
  @root = {}
end

Class Method Details

.from_ranked(ranked_dictionary) ⇒ Trie

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Build a trie from a ranked dictionary hash.

Parameters:

  • ranked_dictionary (Hash{String => Integer}) —

    word → rank

Returns:



13
14
15
16
17
 
# File 'lib/zxcvbn/trie.rb', line 13

def self.from_ranked(ranked_dictionary)
  trie = new
  ranked_dictionary.each { |word, rank| trie.insert(word, rank) }
  trie
end

Instance Method Details

#freeze ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future. 



56
57
58
59
60
61
62
63
 
# File 'lib/zxcvbn/trie.rb', line 56

def freeze
  stack = [@root]
  while (node = stack.pop)
    node.each_value { |v| stack.push(v) if v.is_a?(Hash) }
    node.freeze
  end
  super
end

#insert(word, rank) ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Insert a word and its rank into the trie

Parameters:

  • word (String) —

    the word to insert

  • rank (Integer) —

    the rank/frequency of the word



26
27
28
29
30
31
32
33
 
# File 'lib/zxcvbn/trie.rb', line 26

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

#inspect ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future. 



54
 
# File 'lib/zxcvbn/trie.rb', line 54

def inspect = "#<#{self.class}:0x#{__id__.to_s(16)}>"

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

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

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



39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
# File 'lib/zxcvbn/trie.rb', line 39

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