algorithme de comptage de caractères le plus efficace?

Question

Supposons que vous vouliez compter les occurrences de caractères dans certains textes. Le moyen le plus rapide que je pouvais penser était d'utiliser un tableau comme unsigned char charcounts[256], l'initialiser en zéros, puis regarder chaque caractère dans l'entrée de texte et faire charcounts[c]++. puis recherche linéaire charcounts[] en utilisant deux vars pour garder trace du char le plus bas (jusqu'ici) et son compte, en le remplaçant par un nouveau char/compte quand on en trouve un plus bas, jusqu'à arriver à la fin.

Donc "texte" aurait t = 2, e = 1, x = 1.

Y at-il un moyen plus rapide de le faire?

Answer 1

Cela ressemble un des moyens les plus efficaces pour faire ce que vous décrivez. Je ne suis pas sûr de ce que vous voulez faire avec la deuxième partie, il semble que vous vouliez trouver le personnage qui a le nombre minimum d'occurrences dans les données de tri?

Answer 2

Vous avez décrit deux tâches ici. Le premier consiste à compter le nombre de fois que chaque caractère ASCII se produit dans un flux, et le second essaie de trouver le caractère de fréquence le plus bas.

Le premier algorithme semble comme il est assez efficace. Du haut de ma tête je ne peux pas penser à un moyen plus rapide.

Je suis moins sûr de votre deuxième algorithme, cependant. Vous ne dites pas explicitement pourquoi vous voulez trouver le caractère de fréquence le plus bas, ou quelles sont les données d'entrée, mais je peux imaginer qu'il est facilement possible d'avoir plus d'un caractère qui a un nombre de fréquence de zéro, alors comment voulez-vous différencier entre eux?

Answer 3

La première partie - comptage des fréquences lettre Deux questions à point, en admettant que la langue ici est C ou C++:

• Votre code ne traitera pas des lettres ayant lieu> 255 fois (ou 127 si char arrive à être signé.) Faire "charcounts" un tableau d'ints n'aura probablement pas beaucoup d'impact sur les performances.
• Votre code ne fonctionnera pas pour unicode/caractères internationaux

La deuxième partie - localiser la moindre lettre fréquente

• Si vous avez affaire à des chaînes courtes (« texte », "fred"), puis l'analyse des 256 entrées de votre table est l'étape qui détermine le débit. Vous feriez mieux de suivre la lettre la plus basse fréquence dans la boucle de balayage initiale.
• Mais, si vous ne souhaitez analyser toutes les 256 entrées, vous pouvez sortir de la boucle dès que vous appuyez sur une valeur « un » (ou zéro, si c'est comment votre algorithme est destiné à fonctionner)

Answer 4

La première partie de votre algorithme consiste à compter les caractères. Il s'agit simplement de générer des clés à trier. Si vous savez que vous n'utilisez que des caractères alphabétiques [A-Za-z] *, vous pouvez optimiser votre algorithme en réduisant le nombre de compartiments utilisés, mais ce n'est qu'un petit ajustement.

La deuxième partie est juste une sorte stable - il y a beaucoup de façons de le faire - le wikipedia page on sorting donne un bon résumé.Si vous êtes seulement intéressé par le personnage qui se produit le moins, alors la méthode ("Phase 2") que vous décrivez est probablement aussi efficace que possible. La seule autre façon que je peux penser d'améliorer ceci est si vous pouvez diviser vos lettres dans un nombre fixe de compartiments (disons, 16) uniformément dans la gamme de caractères, puis récursif sur chaque compartiment. Tous les compartiments sans caractères peuvent être jetés, ce qui économise du temps dans la phase de numérisation/tri. De même, si un seau a un caractère, alors c'est fait. Vous voulez également vous assurer que vous ne divisez un seau en 16 autres que lorsque vous savez qu'il y a plus d'un caractère différent.

En utilisant le test de mot comme un exemple (en supposant 4 seaux et caractères seulement des minuscules:

1. génèrent 4 seaux (AG, HM, NT, UZ)
2. diviser le mot test:
   • AG: e,
   • HM:
   • NT: TST
   • UZ:
3. récursion aux autres seaux - (AG a un caractère - ce doit être le moins que nous puissions arrêter
4. Si cela n'a pas été le cas (En ce qui concerne le mot « testicules »), nous pouvons voir HM et UZ sont vides, donc nous aurions seulement besoin de vérifier NT (qui contiendrait tsts).
   • Nous créons 4 godets (N-O, P-Q, R-S et T).
   • Scinder les lettres
   • etc.

L'avantage de cette méthode est que nous n'avons pas eu de scanner chaque lettre. Si la gamme de caractères est de la même taille, alors ces deux méthodes sont au mieux O (n) où n est la longueur de la chaîne (ceci est inévitable puisque nous devons toujours regarder chaque caractère), bien que construisant les listes de caractères dans mon exemple peut rendre l'algorithme aussi mauvais que O (n^2). Cependant, à mesure que la gamme de caractères augmente, en particulier pour les chaînes courtes, l'utilisation de sous-ensembles augmentera considérablement les performances. Pour une chaîne unicode, vous pouvez utiliser une approche hybride - par exemple, séparer tous les caractères non-ascii dans la première phase, et utiliser votre méthode plus simple pour la partie ascii.