Package pywurfl :: Package algorithms :: Package wurfl :: Module strategies
[hide private]
[frames] | no frames]

Source Code for Module pywurfl.algorithms.wurfl.strategies

  1  # pywurfl - Wireless Universal Resource File Tools in Python 
  2  # Copyright (C) 2006-2011 Armand Lynch 
  3  # 
  4  # This library is free software; you can redistribute it and/or modify it 
  5  # under the terms of the GNU Lesser General Public License as published by the 
  6  # Free Software Foundation; either version 2.1 of the License, or (at your 
  7  # option) any later version. 
  8  # 
  9  # This library is distributed in the hope that it will be useful, but WITHOUT 
 10  # ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 
 11  # FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more 
 12  # details. 
 13  # 
 14  # You should have received a copy of the GNU Lesser General Public License 
 15  # along with this library; if not, write to the Free Software Foundation, Inc., 
 16  # 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 
 17  # 
 18  # Armand Lynch <lyncha@users.sourceforge.net> 
 19   
 20  __doc__ = """ 
 21  This module contains the supporting classes for the Two Step Analysis user agent 
 22  algorithm that is used as the primary way to match user agents with the Java API 
 23  for the WURFL. 
 24   
 25  A description of the way the following source is intended to work can be found 
 26  within the source for the original Java API implementation here: 
 27  http://sourceforge.net/projects/wurfl/files/WURFL Java API/ 
 28   
 29  The original Java code is GPLd and Copyright (c) WURFL-Pro srl 
 30  """ 
 31   
 32  __author__ = "Armand Lynch <lyncha@users.sourceforge.net>" 
 33  __copyright__ = "Copyright 2011, Armand Lynch" 
 34  __license__ = "LGPL" 
 35  __url__ = "http://celljam.net/" 
 36  __version__ = "1.2.1" 
 37   
 38  import Levenshtein 
 39   
40 -def ris_match(candidates, needle, tolerance):
41 # Searches for the string which has the longest common substring with the 42 # given needle. If there is not candidates within given tolerance, it 43 # returns the empty string. 44 match = u"" 45 needle_length = len(needle) 46 47 best_distance = -1 48 best_match_index = -1 49 low = 0 50 high = len(candidates) - 1 51 52 # Perfect match: best_distance == needle length() 53 # Best match: best_distance >= tolerance 54 # First match: best_distance == tolerance 55 56 while (low <= high and best_distance < needle_length): 57 mid = (low + high) / 2 58 mid_candidate = candidates[mid] 59 60 distance = longest_common_prefix(needle, mid_candidate) 61 62 if distance > best_distance: 63 best_match_index = mid 64 best_distance = distance 65 66 # Calculate low and high 67 if mid_candidate < needle: 68 low = mid + 1 69 elif mid_candidate > needle: 70 high = mid - 1 71 else: 72 break 73 74 # Candidate is found 75 if best_distance >= tolerance: 76 match = first_of_best_matches(needle, candidates, best_match_index, 77 best_distance) 78 79 return match
80 81
82 -def longest_common_prefix(t1, t2):
83 i = 0 84 t = min(len(t1), len(t2)) 85 86 for j in xrange(0, t): 87 if t1[j] == t2[j]: 88 i += 1 89 else: 90 break 91 return i
92 93
94 -def first_of_best_matches(needle, candidates, best_match_index, best_distance):
95 best_match = candidates[best_match_index] 96 for candidate in reversed(candidates[:best_match_index-1]): 97 if best_distance == longest_common_prefix(needle, candidate): 98 best_match = candidate 99 else: 100 break 101 return best_match
102 103
104 -def ld_match(candidates, needle, tolerance):
105 needle_length = len(needle) 106 user_agent = u"" 107 matches = [(Levenshtein.distance(needle, c), c) for c in candidates if 108 abs(needle_length - len(c)) <= tolerance] 109 if matches: 110 score, user_agent = min(matches) 111 if score > tolerance: 112 user_agent = u"" 113 return user_agent
114