Finden Sie den nächsten Schlüssel in einem Dikton mit String?

Question

Ich versuche einen Weg zu finden, den nächsten Schlüssel zu einer Zeichenkette innerhalb eines Diktons zu finden. Beispiel:

data = {'1a': 'This is 1a', '1d': 'This is 1d', '1f': 'This is 1f', '1e': 'This is 1e'} 
find_nearest(data, '1b') 
#This would return key '1a' 

Ich habe andere Beispiele gefunden, aber die meisten beschäftigen sich mit Zahlen. Beispiel:

data[num] if num in data else data[min(data.keys(), key=lambda k: abs(k-num))] 

ich in der Lage war, einen Code zu finden, die vielversprechend aussah:

from sortedcontainers import SortedDict 
sd = SortedDict((key, value) for key, value in data) 

# Bisect for the index of the desired key. 
index = sd.bisect(200) 

# With that index, lookup the key. 
key = sd.iloc[index] 

# You can also look ahead or behind to find the nearest key. 
behind = sd.iloc[index - 1] 
ahead = sd.iloc[index + 1] 

Also das habe ich versucht, hier ist mein Code:

from sortedcontainers import SortedDict 
data = {'1a': 'This is 1a', '1d': 'This is 1d', '1f': 'This is 1f', '1e': 'This is 1e'} 
sd = SortedDict((key,value) for key,value in data.items()) 

index = sd.bisect('1b') 

key = sd.iloc[index] 
print(key) 

Aber wenn ich diesen Code ausführen es gibt zurück:

1d #Instead of '1a' 

Ich habe tr auf jeden Fall, um den Code zum Laufen zu bringen, aber ich finde es nicht richtig. Kennt jemand einen schnellen und effizienten Weg dies zu erreichen?

Answer 1

Wenn Sie eine Halbierung durchführen, hat der Algorithmus zwei Möglichkeiten, wenn er keine exakte Indexübereinstimmung findet. Es kann den Index des Objekts auf der linken Seite oder den Index des Objekts auf der rechten Seite zurückgeben. Es sieht aus wie bisect ist ein Alias ​​von bisect_right. Sie könnten bisect_left stattdessen verwenden ...

Natürlich ist dies nicht unbedingt näher (Sie haben nicht wirklich definiert, was Sie näher bedeuten). In der Tat wird selbst etwas wie difflib.SequenceMatcher.ratio() wahrscheinlich nicht mit dem Beispiel helfen, da es nur sieht, was das Verhältnis von übereinstimmenden zu nicht passenden Elementen ist.

Sie könnten versuchen, so etwas wie:

def find_closest(sd, expected): 
    index = sd.bisect(expected) 
    closest_lower = sd.iloc[index] 
    try: 
     closest_upper = sd.iloc[index] 
    except IndexError: 
     return closest_lower 

    # assumption -- Your keys are hex values. 
    # this assumption could be completely wrong, but demonstrates 
    # how to think of defining a measure of "closeness" 
    var expected_as_int = int(expected, 16) 
    def distance(val): 
     return int(val, 16) - expected_as_int 

    return min([closest_lower, closest_upper], key=distance) 

Answer 2

Die Art und Weise würde ich dies umzusetzen, indem sie durch den Schlüssel, um iteriert ist, und die Taste mit der kleinsten „Differenz“ zu finden. Da die Schlüssel sortiert sind, wissen Sie, dass Sie sie gefunden haben, sobald die Differenz nicht mehr abnimmt.

def closestKey(data, val): 
    lastKey = None 
    lastDif = None 
    for key in sorted(data.keys()): 
     dif = difference(key, val) #need to figure out difference() 
     if lastDif is not None and dif > lastDif: 
      return lastKey 
     lastDif = dif 
     lastKey = key 

Dies behandelt nicht den Fall, in dem zwei Schlüssel äquidistant sind, wenn das wichtig ist.

Answer 3

Dank @gmilson, das gab mir die Idee, die mir geholfen hat, konnte ich tun, was ich erreichen wollte. Hier ist mein Code für alle Interessierten:

from sortedcontainers import SortedDict 
data = {'1a': 'This is 1a', '1d': 'This is 1d', '1g': 'This is 1g', '1h': 'This is 1h'} 
def find_closest(sd, expected): 
    index = sd.bisect(expected) 
    try: 
     indexAhead = sd.iloc[index] 
    except IndexError: 
     indexAhead = sd.iloc[len(sd.keys()) - 1] 
    if indexAhead == expected: 
     return expected 
    else: 

     try: 
      indexBehindNum = 0 
      indexBehind = sd.iloc[index -1] 
      for char in indexBehind: 
       indexBehindNum += ord(char) 
     except IndexError: 
      pass 
     if not indexBehindNum: 
      return indexAhead 
     else: 
      expectedTotalNum = 0 
      indexAheadNum = 0 
      for char in expected: 
       expectedTotalNum += ord(char) 
      for char in indexAhead: 
       indexAheadNum += ord(char) 
      diffrenceAhead = indexAheadNum - expectedTotalNum 
      diffrenceBehind = indexBehindNum - expectedTotalNum 
      Closest = min([diffrenceAhead, diffrenceBehind], key=abs) 
      if Closest == diffrenceAhead: 
       return indexAhead 
      else: 
       return indexBehind 

sd = SortedDict((key,value) for key,value in data.items()) 

print(find_closest(sd, '1b'))#This will return '1a'! 

Ich bin nicht sicher, ob dies der schnellste und effizienteste, aber ich werde versuchen, weiter zu versuchen, andere Wege zu finden.