Ellissi un insieme di nomi

Question

OK, sono sicuro che qualcuno, da qualche parte, deve aver escogitato un algoritmo per questo già, quindi ho pensato di chiedere prima di andare a (re) inventarlo io stesso.

Ho una lista di stringhe di testo non vuote arbitrarie (immesse dall'utente). Ogni stringa può essere di qualsiasi lunghezza (tranne 0) e sono tutte uniche. Voglio visualizzarli all'utente, ma voglio ridurli a una lunghezza fissa che decido e sostituirne una parte con un'ellissi (...). Il problema è che voglio che tutte le stringhe di output siano uniche.

Per esempio, se ho le stringhe:

• Microsoft Internet Explorer 6
• Microsoft Internet Explorer 7
• Microsoft Internet Explorer 8
• Mozilla Firefox 3
• Mozilla Firefox 4
• Google Chrome 14

quindi non vorrei tagliare le estremità delle stringhe, perché questa è la parte unica (non voglio visualizzare "Microsoft Internet ..." 3 volte), ma è OK tagliare la parte centrale:

• Microsoft ... rer 6
• Microsoft ... rer 7
• Microsoft ... rer 8
• Mozilla Firefox 3
• Mozilla Firefox 4
• Google Chrome 14

Altre volte, la parte centrale potrebbe essere unico, e che avrei voluto tagliare l'estremità:

• Verbale riunione aziendale, 2010/05/25 - Solo per uso interno
• verbale di riunione aziendale, 2010/06/24 - uso interno
• verbale riunione aziendale, 7/23/2010 - solo per uso interno

potrebbe diventare:

• Verbale riunione aziendale, 2010/05/25 ...
• Verbale riunione aziendale, 2010/06/24 ...
• Verbale riunione aziendale, 7/23/2010 ...

Credo che dovrebbe probabilmente mai ellipsize il molto inizio delle corde, anche se che altrimenti sarebbero ammessi, dal momento che sarebbe guardare strano. E immagino che potrebbe ellissi più di un punto nella stringa, ma entro la ragione - forse 2 volte sarebbe OK, ma 3 o più sembra eccessivo. O forse il numero di volte non è importante quanto le dimensioni dei pezzi che rimangono: meno di circa 5 caratteri tra le ellissi sarebbe piuttosto inutile.

Gli ingressi (sia il numero che la dimensione) non saranno eccessivamente grandi, quindi le prestazioni non sono una preoccupazione importante (beh, a patto che l'algoritmo non provi qualcosa di sciocco come enumerare tutte le possibili stringhe finché non trova un set che funzioni!).

Immagino che questi requisiti sembrino piuttosto specifici, ma in realtà sono abbastanza indulgente - sto solo cercando di descrivere quello che ho in mente.

Qualcosa di simile è stato fatto prima? C'è qualche algoritmo o libreria esistente che fa questo? Ne ho cercato su google ma non ho trovato nulla di simile fino ad ora (ma forse sono solo cattivo con Google). Devo credere che qualcuno da qualche parte abbia voluto risolvere questo problema già!

Answer 1

suona come un'applicazione del longest common substring problem.

Sostituire il comune più lunga sottostringa a tutte le stringhe con i puntini di sospensione. Se la stringa è ancora troppo lunga e ti è consentito avere altri puntini di sospensione, ripetere.

Devi capire che potresti non essere in grado di "ellissare" un dato set di stringhe sufficiente a soddisfare i requisiti di lunghezza.

Answer 2

Ordinare le stringhe. Mantieni i primi caratteri X di ogni stringa. Se questo prefisso non è univoco per la stringa prima e dopo, quindi si avanza fino a trovare caratteri univoci (rispetto alla stringa prima e dopo). (Se non vengono trovati caratteri univoci, la stringa non ha parti univoche, vedere il fondo del post) Aggiungi ellissi prima e dopo questi caratteri univoci.

Si noti che questo potrebbe essere ancora divertente:

Microsoft Office -> Micro...ffice 
Microsoft Outlook -> Micro...utlook 

Non so che lingua stai cercando di fare questo, ma ecco un'implementazione di Python.

def unique_index(before, current, after, size): 
    '''Returns the index of the first part of _current_ of length _size_ that is 
     unique to it, _before_, and _after_. If _current_ has no part unique to it, 
     _before_, and _after_, it returns the _size_ letters at the end of _current_''' 
    before_unique = False 
    after_unique = False 
    for i in range(len(current)-size): 
     #this will be incorrect in the case mentioned below 
     if i > len(before)-1 or before[i] != current[i]: 
      before_unique = True 
     if i > len(after)-1 or after[i] != current[i]: 
      after_unique = True 
     if before_unique and after_unique: 
      return i 

    return len(current)-size 

def ellipsize(entries, prefix_size, max_string_length): 
    non_prefix_size = max_string_length - prefix_size #-len("...")? Post isn't clear about this. 

    #If you want to preserve order then make a copy and make a mapping from the copy to the original 
    entries.sort() 

    ellipsized = [] 

    # you could probably remove all this indexing with something out of itertools 
    for i in range(len(entries)): 
     current = entries[i] 

     #entry is already short enough, don't need to truncate 
     if len(current) <= max_string_length: 
      ellipsized.append(current) 
      continue 

     #grab empty strings if there's no string before/after 
     if i == 0: 
      before = '' 
     else: 
      before = entries[i-1] 
     if i == len(entries)-1: 
      after = '' 
     else: 
      after = entries[i+1] 

     #Is the prefix unique? If so, we're done. 
     current_prefix = entries[i][:prefix_size]  
     if not before.startswith(current_prefix) and not after.startswith(current_prefix): 
      ellipsized.append(current[:max_string_length] + '...') #again, possibly -3 

     #Otherwise find the unique part after the prefix if it exists. 
     else: 
      index = prefix_size + unique_index(before[prefix_size:], current[prefix_size:], after[prefix_size:], non_prefix_size) 
      if index == prefix_size: 
       header = '' 
      else: 
       header = '...' 
      if index + non_prefix_size == len(current): 
       trailer = '' 
      else: 
       trailer = '...' 
      ellipsized.append(entries[i][:prefix_size] + header + entries[i][index:index+non_prefix_size] + trailer) 
    return ellipsized 

Inoltre, si dice che le stringhe sono uniche, ma hanno tutte parti uniche? Ad esempio, "Microsoft" e "Microsoft Internet Explorer 7" sono due stringhe diverse, ma la prima non ha parti che siano uniche dal secondo. Se questo è il caso, dovrai aggiungere qualcosa alle tue specifiche su cosa fare per rendere questo caso univoco. (Se si aggiunge "Xicrosoft", "MXcrosoft", "MiXrosoft", ecc. Al mix con queste due stringhe, c'è no stringa univoca più breve della stringa originale per rappresentare "Microsoft") (Un altro modo di pensare esso:.. se si dispone di tutte le possibili stringhe X lettera non li tutto possibile comprimere a X-1 o meno stringhe Proprio come nessun metodo di compressione può comprimere tutti ingressi, in quanto questo è essenzialmente un metodo di compressione)

Risultati dei post originali:

>>> for entry in ellipsize(["Microsoft Internet Explorer 6", "Microsoft Internet Explorer 7", "Microsoft Internet Explorer 8", "Mozilla Firefox 3", "Mozilla Firefox 4", "Google Chrome 14"], 7, 20): 
    print entry 

Google Chrome 14 
Microso...et Explorer 6 
Microso...et Explorer 7 
Microso...et Explorer 8 
Mozilla Firefox 3 
Mozilla Firefox 4 
>>> for entry in ellipsize(["Minutes of Company Meeting, 5/25/2010 -- Internal use only", "Minutes of Company Meeting, 6/24/2010 -- Internal use only", "Minutes of Company Meeting, 7/23/2010 -- Internal use only"], 15, 40): 
    print entry 

Minutes of Comp...5/25/2010 -- Internal use... 
Minutes of Comp...6/24/2010 -- Internal use... 
Minutes of Comp...7/23/2010 -- Internal use...