Class: Wurfl::UserAgentMatcher

Inherits:
Object
  • Object
show all
Defined in:
lib/wurfl/user_agent_matcher.rb

Overview

A class that lists wurfl handsets that match user_agents using the shortest 

Levenshtein distance, also sometimes called the edit distance, 
see http://en.wikipedia.org/wiki/Levenshtein_distance

The implementation of the Levenshtein distance used here is based on the
algorithm found in the Text gem originally written by Paul Battley
([email protected])

The implementation given here makes heavy use of optimizations based on 
the estimation of the lower bound that can be achieved.  Depending on the 
length of the user agent this brought an over all increase by a factor of
about 40, although it renders the code slightly unreadable.  In general the
longer the user agent string and the greater the result distance, the longer
the computation takes.  

Author:  Kai W. Zimmermann ([email protected])

Instance Method Summary collapse

Constructor Details

#initialize(handsets) ⇒ UserAgentMatcher

Constructor Parameters: handsets: A hashtable of wurfl handsets indexed by wurfl_id.



25
26
27
28
29
30
31
 
# File 'lib/wurfl/user_agent_matcher.rb', line 25

def initialize(handsets)
  @handsets = handsets
  @longest_user_agent_length = @handsets.values.inject(0) do |m,hand| 
    hand.user_agent.length > m ? hand.user_agent.length : m
  end
  @d=(0..@longest_user_agent_length).to_a
end

Instance Method Details

#match_handsets(user_agent) ⇒ Object

A method to retrieve a list of the uamatcher’s handsets that match the passed user_agent closest using the Levenshtein distance. Parameters: user_agent: is a user_agent string to be matched Returns: An Array of all WurflHandsets that match the user_agent closest with the same distance The Levenshtein distance for these matches



41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
# File 'lib/wurfl/user_agent_matcher.rb', line 41

def match_handsets(user_agent)
  rez = []
  shortest_distance = [user_agent.length, @longest_user_agent_length].max
  s = user_agent.unpack(unpack_rule)

  @handsets.values.each do |hand|    
    distance = levenshtein_distance(user_agent, hand.user_agent, shortest_distance, s)
    # found a shorter distance match, flush old results 
    rez.clear if shortest_distance > distance

    if shortest_distance >= distance
      # always add the first handset matched and each that has the same 
      # distance as the shortest distance so far 
      rez << hand
      shortest_distance = distance
    end

    break if shortest_distance == 0
  end

  return rez, shortest_distance 
end