Wyszukiwanie najczęstszej postaci w ciągu znaków

Question

Znalazłem ten problem programistyczny, patrząc na ogłoszenie o pracy na SO. Pomyślałem, że to całkiem interesujące i jako początkujący programista Pythona spróbowałem go rozwiązać. Jednak uważam, że moje rozwiązanie jest dość ... niechlujne ... Czy ktoś może przedstawić sugestie, aby zoptymalizować go lub uczynić go czystszym? Wiem, że to dość trywialne, ale dobrze się bawiłem, pisząc to. Uwaga: Python 2.6

problem:

Write pseudo-kod (lub rzeczywisty kod) dla funkcji, które odbywają się w ciąg znaków i zwraca list, który pojawia się najczęściej w tego łańcucha.

Moja próba:

import string 

def find_max_letter_count(word): 

    alphabet = string.ascii_lowercase 
    dictionary = {} 

    for letters in alphabet: 
     dictionary[letters] = 0 

    for letters in word: 
     dictionary[letters] += 1 

    dictionary = sorted(dictionary.items(), 
         reverse=True, 
         key=lambda x: x[1]) 

    for position in range(0, 26): 
     print dictionary[position] 
     if position != len(dictionary) - 1: 
      if dictionary[position + 1][1] < dictionary[position][1]: 
       break 

find_max_letter_count("helloworld") 

wyjściowa:

>>> 
('l', 3) 

Updated przykład:

find_max_letter_count("balloon") 
>>> 
('l', 2) 
('o', 2) 

Answer 1

Istnieje wiele sposobów, aby to zrobić krótsze. Na przykład, można użyć klasy Counter (w Pythonie 2.7 lub nowszy):

import collections 
s = "helloworld" 
print(collections.Counter(s).most_common(1)[0]) 

Jeżeli nie masz, że można ręcznie zrobić zgadzają (2.5 lub nowszym ma defaultdict):

d = collections.defaultdict(int) 
for c in s: 
    d[c] += 1 
print(sorted(d.items(), key=lambda x: x[1], reverse=True)[0]) 

Powiedziawszy to, nie ma nic strasznie złego w realizacji.

Answer 2

Oto kilka rzeczy zrobiłbym:

• Zastosowanie collections.defaultdict zamiast dict uruchamiasz ręcznie.
• Skorzystaj z wbudowanego sortowania i funkcji maksimum, takich jak max, zamiast samemu go rozwiązać - jest to łatwiejsze.

Oto mój wynik końcowy:

from collections import defaultdict 

def find_max_letter_count(word): 
    matches = defaultdict(int) # makes the default value 0 

    for char in word: 
     matches[char] += 1 

    return max(matches.iteritems(), key=lambda x: x[1]) 

find_max_letter_count('helloworld') == ('l', 3) 

Answer 3

Jeśli używasz Pythona 2.7, można szybko zrobić to za pomocą modułu kolekcjach. collections to moduł struktur danych dotyczących wysokich wyników. Czytaj więcej na http://docs.python.org/library/collections.html#counter-objects

>>> from collections import Counter 
>>> x = Counter("balloon") 
>>> x 
Counter({'o': 2, 'a': 1, 'b': 1, 'l': 2, 'n': 1}) 
>>> x['o'] 
2 

Answer 4

Jeśli chcesz mieć wszystkie znaki z maksymalną liczbą zliczeń, a następnie można zrobić zmianę na jednym z dwóch pomysłów proponowanych do tej pory:

import heapq # Helps finding the n largest counts 
import collections 

def find_max_counts(sequence): 
    """ 
    Returns an iterator that produces the (element, count)s with the 
    highest number of occurrences in the given sequence. 

    In addition, the elements are sorted. 
    """ 

    if len(sequence) == 0: 
     raise StopIteration 

    counter = collections.defaultdict(int) 
    for elmt in sequence: 
     counter[elmt] += 1 

    counts_heap = [ 
     (-count, elmt) # The largest elmt counts are the smallest elmts 
     for (elmt, count) in counter.iteritems()] 

    heapq.heapify(counts_heap) 

    highest_count = counts_heap[0][0] 

    while True: 

     try: 
      (opp_count, elmt) = heapq.heappop(counts_heap) 
     except IndexError: 
      raise StopIteration 

     if opp_count != highest_count: 
      raise StopIteration 

     yield (elmt, -opp_count) 

for (letter, count) in find_max_counts('balloon'): 
    print (letter, count) 

for (word, count) in find_max_counts(['he', 'lkj', 'he', 'll', 'll']): 
    print (word, count) 

Daje to, na przykład:

lebigot@weinberg /tmp % python count.py 
('l', 2) 
('o', 2) 
('he', 2) 
('ll', 2) 

działa w dowolnej kolejności: słowa, ale też [ 'Dzień dobry', 'Dzień dobry' , "bonjour"], na przykład.

Struktura jest bardzo skuteczna w znajdowaniu najmniejszych elementów sekwencji bez jej całkowitego sortowania. Z drugiej strony, ponieważ nie ma zbyt wielu liter w alfabecie, prawdopodobnie można również przejść przez posortowaną listę zliczeń, aż do momentu, gdy nie zostanie już znaleziona maksymalna liczba, bez narażania się na poważną utratę prędkości.

Answer 5

Oto sposób na znalezienie najczęstszą postacią używając słownika

message = "hello world" 
d = {} 
letters = set(message) 
for l in letters: 
    d[message.count(l)] = l 

print d[d.keys()[-1]], d.keys()[-1] 

Answer 6

def most_frequent(text): 
    frequencies = [(c, text.count(c)) for c in set(text)] 
    return max(frequencies, key=lambda x: x[1])[0] 

s = 'ABBCCCDDDD' 
print(most_frequent(s)) 

frequencies jest listą krotek, które liczą znaki jak (character, count). Maksymalnie stosujemy krotki, używając count i zwracamy krotkę character. W przypadku remisu rozwiązanie to wybierze tylko jeden.

Answer 7

#file:filename 
#quant:no of frequent words you want 

def frequent_letters(file,quant): 
    file = open(file) 
    file = file.read() 
    cnt = Counter 
    op = cnt(file).most_common(quant) 
    return op