Ellipsiser un ensemble de noms

Question

OK, je suis sûr que quelqu'un, quelque part, a dû trouver un algorithme pour cela, alors j'ai pensé que je demanderais avant de partir le (ré) inventer moi-même.

J'ai une liste de chaînes de texte non vides (entrées par l'utilisateur). Chaque chaîne peut avoir n'importe quelle longueur (sauf 0), et elles sont toutes uniques. Je veux les afficher à l'utilisateur, mais je veux les couper à une longueur fixe que je décide, et remplacer une partie d'entre eux avec une ellipse (...). Le problème est que je veux que toutes les chaînes de sortie soient uniques.

Par exemple, si j'ai les cordes:

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

alors je ne voudrais pas couper les extrémités des chaînes, parce que c'est la partie unique (ne veut pas afficher "Microsoft Internet ..." 3 fois), mais c'est OK pour couper la partie du milieu:

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

D'autres fois, la partie centrale est peut-être unique, et je voudrais à rogner la fin:

• Procès-verbal de la réunion d'entreprise, 5/25/2010 - Usage interne uniquement
• Procès-verbal de la réunion d'entreprise, 6/24/2010 - usage interne seulement
• Procès-verbal de la réunion d'entreprise, 7/23/2010 - usage interne uniquement

pourraient devenir:

• Procès-verbal de la réunion d'entreprise, 5/25/2010 ...
• Procès-verbal de la réunion d'entreprise, 6/24/2010 ...
• Procès-verbal de la réunion d'entreprise, 7/23/2010 ...

Je suppose que cela ne devrait probablement jamais ellipsize le très début des cordes, même si cela serait permis par ailleurs, car cela l'air bizarre. Et je suppose que cela pourrait ellipsiser plus d'un endroit dans la chaîne, mais dans des limites raisonnables - peut-être que 2 fois serait OK, mais 3 ou plus semble excessif. Ou peut-être que le nombre de fois n'est pas aussi important que la taille des morceaux qui restent: moins d'environ 5 caractères entre les ellipses serait plutôt inutile.Les entrées (à la fois le nombre et la taille) ne seront pas très grandes, donc la performance n'est pas une préoccupation majeure (enfin, tant que l'algorithme n'essaie pas d'énumérer toutes les chaînes possibles jusqu'à ce qu'il trouve un ensemble ça marche!).

Je suppose que ces exigences semblent assez spécifiques, mais je suis assez indulgent - j'essaie juste de décrire ce que j'ai en tête.

Est-ce que quelque chose comme ceci a déjà été fait? Y a-t-il un algorithme ou une bibliothèque existant qui le fait? J'en ai googlé quelques-uns mais je n'ai rien trouvé de tel jusqu'à présent (mais peut-être que je suis juste mauvais pour googler). Je dois croire que quelqu'un a déjà voulu résoudre ce problème!

Answer 1

Il ressemble à une application du longest common substring problem.

Remplacer la plus longue chaîne commune à toutes les chaînes avec des points de suspension. Si la chaîne est encore trop longue et que vous pouvez avoir une autre ellipse, répétez.

Vous devez réaliser que vous ne pourrez peut-être pas «ellipsiser» un ensemble donné de chaînes pour répondre aux exigences de longueur.

Answer 2

Trier les chaînes. Gardez les X premiers caractères de chaque chaîne. Si ce préfixe n'est pas unique à la chaîne avant et après, avancez jusqu'à trouver des caractères uniques (par rapport à la chaîne avant et après). (Si aucun caractère unique n'est trouvé, la chaîne n'a pas de partie unique, voir en bas de la publication) Ajouter des ellipses avant et après ces caractères uniques.

Notez que cela pourrait encore paraître drôle:

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

Je ne sais pas quelle langue vous cherchez à faire, mais voici une implémentation de Python. En outre, vous mentionnez que la chaîne elle-même est unique, mais ont-elles toutes des parties uniques? Par exemple, "Microsoft" et "Microsoft Internet Explorer 7" sont deux chaînes différentes, mais la première n'a aucune partie unique par rapport à la seconde. Si tel est le cas, vous devrez ajouter quelque chose à vos spécifications sur ce qu'il faut faire pour rendre ce cas non ambigu. (Si vous ajoutez "Xicrosoft", "MXcrosoft", "MiXrosoft", etc. au mélange avec ces deux chaînes, il y a non chaîne unique plus courte que la chaîne d'origine pour représenter "Microsoft") (Une autre façon de penser à it: si vous avez toutes les chaînes de lettre X possibles, vous ne pouvez pas les compresser toutes en X-1 ou moins, comme aucune méthode de compression ne peut compresser toutes les entrées, car il s'agit essentiellement d'une méthode de compression.)

Résultats de l'article original:

>>> 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...