Meilleur algorithme pour raccourcir les mots anglais

Question

J'ai quelques codes uniques qui sont générés à partir de chaînes de caractères (ex: noms d'hôtes de site Web) dans divers composants indépendants de mon application. Ces codes sont destinés à être utilisés uniquement par des machines, donc je voudrais les garder aussi courtes que possible.

L'algorithme ci-dessous serait appliqué à chaque mot de la chaîne. Les mots de sortie seraient concaténés avec un tiret pour générer le code unique.

The current algorithm I have used: 

- Skip word if length is less than 6 

- Leave first character as is 

- Remove every wowel in the word from the second character onwards 

1. architectural digest eu => archtctrl-DGST-eu
2. pied arizona Magazine => Arzn-fthlls-MGZN

Y at-il une meilleure façon de réduire un mot anglais laissant aussi reconnaissable que possible à un lecteur humain?

La sortie doit être déterministe et produire la même version abrégée lorsqu'elle est exécutée sur la même entrée.

Un bon algorithme devrait également minimiser le nombre de collisions pour des mots de même orthographe.

Answer 1

J'ai des codes uniques qui sont générés à partir de chaînes

Je crains que ce soit pas vrai. Il y a beaucoup de mots anglais qui réduiront au même «mot de code» quand dépouillé de leurs voyelles. Par exemple, «quitter» -> «vivre» Étant donné que c'est assez rare, cela pourrait encore causer des problèmes. A quel point est-il important que ces mots de code restent lisibles par l'homme si, comme vous le dites, ils sont destinés à être utilisés uniquement par des machines? Si ce n'est pas si important, je suggérerais de chercher dans quelques algorithmes de compression plus simples comme Huffman Coding ou LZW Compression. Ensuite, si l'utilisateur a besoin de voir la traduction du mot de code, il suffit de le décompresser.

Si vous devez le garder lisible, je ne suis pas sûr qu'il y ait beaucoup plus que vous pouvez faire pour le raccourcir. Vous pouvez jeter un coup d'œil sur les racines spécifiques du latin et du grec, et déterminer si vous pouvez les raccourcir à la main, puis les remplacer automatiquement.

Alternativement, vous pourriez vous tourner vers une approche phonétique. Recherche automatique la prononciation du mot, puis voir si elle est plus courte (ou elle-même peut être compressée, en prenant 'cee' à 'C', ou 'kay' à 'K'). Ce serait beaucoup plus de temps et de ressources processeur, mais c'est toujours une option si vous avez vraiment besoin de codes courts mais lisibles.

Answer 2

Ce que vous générez ressemble à ce qu'on appelle un "slug". Il existe de nombreuses bibliothèques pour gérer cela pour les blogs ou les générateurs de sites qui devraient répondre à vos besoins.Voici un exemple d'utilisation d'une bibliothèque Python appelé slugify:

txt = "___This is a test ---" 
r = slugify(txt) 
self.assertEqual(r, "this-is-a-test") 

bibliothèques Slug fonctionnent généralement comme ceci:

1. en remplaçant les caractères linguistiques non-ascii via une cartographie (ex: 影師嗎 -> ying-shi-ma)
2. remplacer accentués lettres latines avec des équivalents ascii via un mappage (ex: C'est déjà l'été. -> c-est-deja-l-ete)
3. supprimer les espaces de début et de fin/ponctuation
4. Convertir les espaces et la ponctuation des tirets, l'effondrement de plusieurs traits dans une ligne à un seul tableau de bord

Si vous voulez faire des limaces plus court que vous pouvez supprimer les voyelles ou, plus simplement, utiliser une longueur maximale.