11
votes

Structure de données pour le dictionnaire multilingue?

Sommaire d'une ligne: Suggérez une structure de données optimale (de recherche / compacité de recherche / compacité) pour un dictionnaire multilingue représentant principalement les langues indo-européennes (liste en bas).

Dites que vous souhaitez construire certaines structures de données pour mettre en place un dictionnaire multilingue pour dire les langues européennes top-n (n ~ 40) sur Internet, classement le choix de la langue Par nombre de pages Web (liste approximative des langues données au bas de cette question). L'objectif est de stocker le vocabulaire de travail de chaque langue (c'est-à-dire 25 000 mots pour l'anglais, etc.) Les noms appropriés sont exclus. Je ne sais pas si nous stockions des pluriels, des conjugités verbales, des préfixes, etc. ou ajoutez des règles spécifiques à la langue sur la manière dont elles sont formées de singuliers ou de tiges verbales. De plus, votre choix sur la manière dont nous encodons et gérons les accents, les diphtongues et les caractères spéciaux spécifiques à la langue par exemple. Peut-être que possible si possible nous Translithathere choses (par exemple, Romanize allemand ß comme 'ss', puis ajoutez une règle pour la convertir). Évidemment, si vous choisissez d'utiliser 40-100 caractères et une trie, il y a beaucoup trop de branches et la plupart d'entre eux sont vides.

Définition de la tâche: Quelle que soit la structure de données que vous utilisez, vous devez faire les deux éléments suivants:

  1. L'opération principale en recherche est de recevoir rapidement une indication "Oui, il s'agit d'un mot valide dans les langues A, B et F mais non C, D ou E '. donc, si n = 40 Langues, votre structure retourne rapidement 40 booléens.
  2. L'opération secondaire consiste à renvoyer un point de pointeur / objet pour ce mot (et toutes ses variantes) pour chaque langue (ou null si elle était invalide). Ce pointeur / objet pourrait être défini par l'utilisateur par exemple. La Partie de la parole et de la définition du diconaire / Thesaurus Similes / liste des traductions dans les autres langues / ... Cela pourrait être spécifique à la langue ou indépendante de la langue. une définition partagée de pizza )

    et la métrique principale pour l'efficacité est un compromis d'une compacité (à travers toutes les n langues n) et b) la vitesse de recherche . Temps d'insertion non important. La contrainte de compacité exclut les approches de mémoire-gaspillettes telles que "Gardez un hachage séparé pour chaque mot" ou "gardez un séparé pour chaque langue, et chaque mot dans cette langue" . / p>

    SO:

    1. Quelles sont les structures de données possibles, comment se classent-ils sur le Courbe de vitesse / de compacité de la recherche?
    2. Avez-vous une structure unifiée pour toutes les N langues ou la partition par Partition. les langues germaniques dans une sous-structure, slave dans un autre, etc.? ou juste n structures séparées (qui vous permettrait de Huffman-Encode)?
    3. Quelle représentation utilisez-vous pour des caractères, des accents et des caractères spéciaux spécifiques à la langue?
    4. Idéalement, donnez un lien vers l'algorithme ou le code, en particulier Python ou autre C. -

      (J'ai vérifié ainsi et il y a eu des questions connexes mais pas cette question exacte. Certainement pas à la recherche d'une base de données SQL. Un article de 2000 qui pourrait être utile: " Estimation de la langue anglaise et non anglaise sur le www "- Grefenstette & Nioche . Et un Liste des dictionnaires multilingues ) Ressources: Deux dictionnaires multilingus en ligne sont Interglot (EN / GE / NL / FR / SP / SE) et Lookwayp (EN <-> FR / GE / SP / NL / PT) .


      Langues à inclure:

      Probablement principalement Langues indo-européennes pour la simplicité: anglais, français, espagnol, allemand, Italien, suédois + albanais, tchèque, danois, néerlandais, estonien, finnois, hongrois, islandais, letton, litton, norvégien, polonais, portugais, roumain, russe, slovène croate, slovaque, slovène + breton, catalan, gaélique, espéranto, gaélique , Gallois

      Incluez probablement le russe, le slave, le turc, exclure l'arabe, l'hébreu, l'iranien, l'Indien, etc. peut également inclure la famille malaise. Dis-moi ce qui est réalisable.


26 commentaires

Connectez-vous des mots localisés? (Localisé est la mauvaise orthographe!)


Je ne sais pas, obtenez des chiffres sur la manière dont ils augmentent la taille du vocabulaire? Parlons-nous de variantes du même mot (par exemple, nous-utilisons-nous contre britannique) ou en ajoutant des mots entièrement nouveaux? Je pense seulement à un vocabulaire de travail (par exemple 25 000 mots en anglais), pas un lexique complet. Disons: un peu, jusqu'au point qu'il ne nuit pas à la tâche principale de construire une structure multilingue pour N langues.


Variations, et est le genre de chose que Mac OS X semble prendre en charge par défaut.


@Arafangion: Ni localisé ni localisé n'est faux parce qu'ils sont locali * ed.


@Alex: Whatevs. Je suis vraiment intéressé par des réponses de qualité à cette question ... Quelqu'un doit avoir une suggestion.


Ce n'était pas une réponse à la question, juste un simple commentaire et à quelqu'un d'autre. Maintenant, qu'entendez-vous de ce que vous voulez dire vite? Quelle est la lente acceptable? 1 seconde? dix? 0.01? Cela inclura-t-il réellement des définitions réelles ou simplement des liens? Comment compact devrait-il être comparé au contenu non compressé?


Je n'ai pas eu de chiffres difficiles à l'esprit, mais l'application que je pensais était de pouvoir identifier la langue dans de courts messages sans contexte (tels que des postes dans un bulletin / média social / session de chat / liste de diffusion / de la liste de diffusion / moteur de recherche ), en temps réel. Donc, disons Le temps de recherche doit <10ms et ci-dessous que vous pouvez optimiser pour la compacité ou la vitesse supplémentaire . Étant donné que l'objectif principal était l'identification de la langue, je m'en fiche que s'il ne contient que des indications sur les définitions.


@Alex: C'était mon point de vue, en ce qui concerne les VS localisées localisées. :)


Avez-vous les données ou les exemples de données? Je pense que le mieux que nous puissions faire est d'essayer quelques approches et de choisir le meilleur.


Non, c'est juste une question générale que j'ai pensée. Je pense que vous êtes accroché à la compression dans une seule langue, par opposition à Compactness entre les langues . Vous devez esquisser des grandes lignes générales de la manière de gérer la cartographie des accents et des caractères spéciaux lors de la construction du dictionnaire, de conserver le facteur de ramification. par exemple. Vous les romanisez-vous? Donnez-leur une lettre séparée? Établir des correspondances entre les langues? ou bien quoi? Es-tu ex. Partition La N Langues dans des sous-documents multilingues totalement séparés (germanique, romance, slave, balte, turc turc, austronésien ...)?


Il est difficile de prédire la manière dont tout cela va compresser sans que tout ce qui soit, surtout s'il y a plus d'une langue et que vous ne voulez pas les séparer dans l'espoir que les mots partagés et similaires contribueront à mieux compresser. Voir toutes les bonnes techniques de compression exploiter des fonctionnalités de données spécifiques, elles s'appuient sur des statistiques. En outre, une question générale comme celle-ci est proche d'être considérée comme "non constructive" ou "pas une question réelle".


Alex, vous êtes parfaitement capable de localiser des dictionnaires pour tout ou partie des n = 40 langues que j'ai identifiées (j'ai déjà donné des liens à plusieurs), ce qui fait la compression entre les langues et nous dire un algorithme optimal. Les statistiques sont des "mots qui se produisent légalement dans un vocabulaire de travail de toutes ces langues (y compris les pluriels nominaux, les déclensions de verbe)". Si vous voulez un sous-ensemble, essayez simplement le Top-5 EUROPEENNES LANGUES PAR URISERCOUNTS : Anglais, Espagnol, Portugais, allemand, français.


Il est assez difficile d'obtenir un dictionnaire avec toutes les formulaires de mots. La plupart ne vous donnent que la forme de base. Vous pouvez, bien sûr, extraire des mots d'un grand corpus texte, mais à vous de trouver tous les formulaires de mots les plus infligés et les associer avec des formes de base. Cela nécessite que vous appreniez réellement un peu de grammaire et de morphologie à chaque langue et à la mise en œuvre ou à la recherche de code pour faire ce travail. BTW, les verbes espagnols ont environ 100 formes en raison de diverses tendances, 3 personnes, 2 comptes et l'habitude de collage de pronoms à la fin des formes de verbe. Environ 10% des verbes espagnols sont assez irréguliers.


Ok, donc nous voulons peut-être un dictionnaire (multilingue) qui correspond à des tiges verbales possibles, puis essaie de correspondre à N = 40 règles de conjugaison spécifiques à la langue. Une combinaison d'un dictionnaire et d'une grammaire, essentiellement. (Vous avez des liens vers le code pour les règles de conjugaison?) Pouvez-vous aborder les autres parties de la question, à savoir une cartographie efficace de caractères spéciaux, entre les langues?


Si votre seul but est de stocker (et de récupérer) les mots et les descriptions, pourquoi pas simplement utiliser une modélisation de base de données relationnelle unie? Il y a peut-être des problèmes d'orthographe WRT et de homonymes, mais cela n'a pas l'air insoluble. Si votre but inclut également la classification du texte inconnu, vous pouvez utiliser une variante de chaîne markov «annotée».


@wildplasser: Pouvez-vous comparer la compacité et les heures de recherche d'une approche de RDB pour (dire) une trie? Avez-vous plusieurs entrées pour plusieurs langues? Faites-vous (spécifique à la langue) stemming?


Non, je ne dis pas que vous devriez faire la mise en œuvre dans SQL. J'ai dit que vous devriez faire la modéliser comme dans les bases de données SQL. BTW: Je ne pense pas que vous devriez faire une correction d'erreur stemming ou d'orthographe ou de détection d'homonymation. Vous devriez accepter n'importe quel jeton et laisser une couche intermédiaire s'en occuper de cela. ("Chaque problème peut être résolu par une couche supplémentaire d'indirection"). Pour référence: Voir le papier de conception d'origine pour Google / Pagerank: chaque jeton a été accepté (ou ignoré) et le back-end a pris soin de la sémantique; Il n'y a pas de cas particulier. Le dictionnaire a été conçu de manière à ce qu'il soit adapté au cœur.


@wildplasser: Je demande une compacité de compacité et je vous demande seulement de stocker un vocabulaire de travail, pas accepter tous les jetons. Quelle que soit la modélisation dans SQL, je veux seulement savoir quelle est la structure finale, pour cette application ? Quant aux papiers Paperank, avez-vous voulu dire page, Brin, Motwani, Winograd " Le classement de la citation PageRank: apporter une commande au web »(1998) ?


@wildplasser: N'oubliez pas que nous devons stocker une définition spécifique à la langue, pas seulement une liste de mots langagiers-agnostiques sans plus d'informations, je ne vois donc pas comment le pagerank est applicable. Je ne vois même pas que vous pourriez simplement accepter tous les jetons, vous devez savoir quelle langue (s) langue (s) et sont légales, ce qui implique la surveillance humaine. Si quelqu'un soumet un orthographe, l'acceptez-vous? Comment désambiguez-vous entre Mates (verbe) et Mates (nom pluriel) ?


Non, je voulais dire un article plus ancien décrivant le dictionnaire brut, la binning et la partie index inversée. Pour le tokeniser, il est plus facile d'accepter n'importe quel jeton . période. Les trucs spécifiques à la langue (tels que la tige, les homonymes, la spécificité de la langue) peuvent être pris en charge dans une couche ultérieure (N <-> m), mappage vers un domaine sémantique "conceptuel". Prenez par exemple la jeton "boucle" qui (en anglais) pouvait signifier l'itération ou itérer {subst, verbe} ou en hollandaise, baril {verbe: tige = "lopen", nom: "baril d'une arme à feu"} est toujours le même jeton. Pour garder le Tokeniser simple, il devrait être accepté tel quel.


Si quelqu'un soumet un orthographe (populaire), comment votre index apprend-t-il automatiquement à distinguer entre héros (pluriel de héros) vs héros (= sandwichs) ? ou en français héros ? Qu'en est-il des utilisateurs de langue étrangère qui a simplement tapé dans leur mot étranger sans accents, comment pouvons-nous éviter de l'indexation à tort?


@Wildplasser: Veuillez soumettre une réponse déjà avec vos excellents commentaires! Je pose des questions sur la structure finale , pas les intermédiaires. Par conséquent, je pense que c'est sans importance que Loop a des homonymes entre les langues à la phase de jeton et d'indexation, car nous savons finalement un dictionnaire multilingue doit séparer ses significations néerlandaises et anglaises. Ne pas demander les détails de la mise en œuvre sous le capot de la manière dont nous avons construit cela.


C'est bon, je le ferai. Mais j'ai bien peur, j'ai besoin de SQL pour illustrer mon point ;-) L'idée de la signification néerlandaise et anglaise est que vous devrez séparer le jeton de son rôle et de son sens. C'est juste un niveau supplémentaire d'indirection. (En SQL Parliance: une ou deux tables pour raconter les deux domaines)


@Wildplasser: OK mais prenez-le que la tokenision est un problème résolu et même pas le problème d'intérêt ici. Ce que vous voulez vraiment résoudre, c'est comment apprendre et indexer séparément les différentes significations de Baba sur anglais , Français , espagnol , portugais , Turc . Lorsqu'il est utilisé comme un nom, sa signification dépend de la langue: "Gâteau du rhum", "Salive", "Père" ...


Strictement je voulais dire homographe interlingual pas homonyme.


La chose "interlingual momographe" est exactement la raison pour laquelle j'ai hésité entre une et deux couches intermédiaires (tables "SQL" ...)


5 Réponses :


5
votes

Je ne suis pas sûr que cela fonctionnerait ou non pour votre problème particulier, mais voici une idée à penser.

Une structure de données souvent utilisée pour des représentations rapides et compactes de la langue est une DFA d'état minimum pour la langue. Vous pouvez construire cela en créant une trie pour la langue (qui est en soi un automate pour reconnaître les chaînes dans la langue), puis en utilisant des algorithmes canoniques pour la construction d'une DFA d'état minimum pour la langue. Cela peut nécessiter une quantité énorme de temps de prétraitement, mais une fois que vous avez construit l'automate, vous aurez une recherche extrêmement rapide des mots. Vous venez de commencer à l'état de départ et de suivre les transitions étiquetées pour chacune des lettres. Chaque état pourrait coder (peut-être) un codage de valeur de 40 bits pour chaque langue si l'état correspond ou non à un mot dans cette langue.

Comme différentes langues utilisent différents alphabets, il pourrait une bonne idée de séparer chaque langue par alphabet afin de pouvoir minimiser la taille de la table de transition pour l'automate. Après tout, si vous avez des mots utilisant les alphabets latins et cyrilliques, les transitions d'état pour les États représentant des mots grecques seraient probablement tous à l'état mort sur des lettres latines, tandis que les transitions pour les caractères grecs pour les mots latins seraient également à l'état mort. . Avoir plusieurs automates pour chacun de ces alphabets pourrait donc éliminer une énorme quantité d'espace gaspillé.


10 commentaires

Vous n'avez pas dit comment vous gérez des accents? Lorsque vous décidez de «séparer chaque langue par alphabet», une possibilité est de cartographier l'équivalent latin, grec et cyrillique les uns des autres par exemple. par Romanisation E.G. de grec . Cela devient inefficace où vous mappez un personnage à deux paragraphe latins. χ → ch.


Je ne suis vraiment pas sûr de la meilleure façon de faire cela est. Mon inside au départ serait de traiter latin de base avec des accents comme distinct de grec et de cyrillique, mais honnêtement, je ne sais pas si c'est une bonne idée. Je n'ai pas beaucoup d'expérience en travaillant avec plusieurs langues, alors peut-être que c'est clairement un choix médiocre et la romanisation est une bonne idée.


En ce qui concerne l'efficacité, ce n'est peut-être pas qu'une grande partie d'un coup (cependant, je ne suis pas sûr de la façon dont cela serait mal). Dans le pire des cas, je supposerais que ce serait une soufflage 2x, qui est linéaire de la taille de l'entrée.


Eh bien, avez-vous voulu dire utiliser n structures de données pour n langues? C'est plus grand. Il est sûrement possible de fusionner au moins les principales langues romance (français, espagnol, portugais et peut-être italien)?


Non, vous voudrez certainement fusionner la plupart des langues de romance ensemble! Je signifiais principalement la classification par alphabet pour éviter d'avoir une énorme espace gaspillé dans chaque table.


S'il vous plaît dites-moi à peu près combien d'alphabets qui signifie pour la liste de langue que j'ai donnée? Et surtout lorsque vous fusionnez des langues, vous devrez me dire comment vous manipulez Diacriticals . Utilisation espagnole et portugaise tilde à des fins différentes, alors que le français ne l'a pas du tout; Comment éviter d'ajouter ~ 20 caractères supplémentaires inutiles avec des accents?


@TemplatetyTypedef nous a laissé Continuez cette discussion en chat


Cette solution est-elle une option pour un dictionnaire qui est constamment mis à jour par la saisie de l'utilisateur?


@Suragch au meilleur de ma connaissance Il n'y a pas de moyen simple d'utiliser des automates minimum-State avec la mise à jour des listes de mots car les modifications mineures du mot peuvent avoir de profonds changements sur l'automate minimum de l'état. Cependant, j'espère être prouvé comme tort!


@Templatetypedef, c'est ce que j'avais peur, mais j'essaie de vérifier toutes les options viables avant de commencer un tel projet.



0
votes

facile.

construire un Fonction de hachage minimale et parfaite pour vos données (Union de tous les dictionnaires, construction Le hash Halline), et profitez o (1) lookup pour le reste de l'éternité.

tire parti du fait que vos clés sont connues de manière statique. Ne se soucie pas de vos accents et ainsi de suite (normalisez-les avant le hachage si vous voulez).


2 commentaires

Non, cela ne traite pas de la compacité ou du chevauchement entre les langues. Homme, Mankind, Manhole, Mangiare, Mannschaft ...


Vous ne faites pas la partie secodarienne non plus: Vous devez également renvoyer un pointeur à la définition correspondante dans chacune des n langues . Le défi n'était pas seulement de hacher un grand ensemble de booléens pour n = 40 langues, tout le monde peut le faire. Vous souhaitez ajouter de l'efficacité sur le stockage des choses afin que vous n'ayez pas besoin d'un pointeur pour chaque conjugaison ou nom pluriel du nom. Considérez en anglais salue / salutations / saluée / greeter / salutation / salutations doit-le tous utiliser le même pointeur. Maintenant, comment généraliser ce type de structure entre les langues?



4
votes

Je ne gagnerai pas de points ici, mais certaines choses.

Un dictionnaire multilingue est une entreprise importante et fastidieuse. Vous n'avez pas parlé en détail sur les utilisations exactes pour lesquelles votre dictionnaire est destiné: statistique probablement, ne traduisant probablement pas, non grammaticale, .... Différentes utilisations nécessitent des données différentes à collecter, par exemple, classant «allé» comme passé.

Formulez d'abord vos premières exigences dans un document et avec un prototype d'interface programmé. Demander des structures de données avant la conception algorithmique que je vois souvent pour une logique commerciale complexe. On démarrerait alors mal, risquer . Ou optimisation prématurée, comme cette romanisation, qui pourrait n'avoir aucun avantage et une bidon de barrectivité. P>

Peut-être que vous pouvez commencer par des projets actifs comme Reta Vortaro ; Son XML pourrait ne pas être efficace, mais vous donner des idées d'organisation. Il existe plusieurs projets linguistiques académiques forts>. L'aspect le plus pertinent pourrait être stemming strong>: reconnaissance salutation / saluée / saluée / salutation / salutations / salutations em> (@smci) comme appartenant à la même entrée (majeure). Vous voulez prendre les stemmers déjà programmés; Ils sont souvent bien testés et déjà appliqués dans des dictionnaires électroniques. Mon avantage serait de la recherche em> ces projets sans perdre beaucoup d'énergie, d'une impulsion, d'eux; Juste assez pour collecter des idées et voir où ils pourraient être utilisés. p>

Les structures de données on peut penser, sont imphomes d'importance secondaire. Je serais Collecter tout d'abord dans une base de données bien définie forte>, puis générer les structures de données utilisées du logiciel strong>. Vous pouvez ensuite comparer et mesurer des alternatives. Et cela pourrait être pour un développeur la partie la plus intéressante, créant une belle structure de données et algorithme. P>


une réponse forte> p> p> p> P> P>

exigence: strong> p>

Carte de Word à la liste de [Langue, Définition Référence]. Liste des définitions. P>

Plusieurs mots peuvent avoir la même définition, d'où la nécessité d'une référence de définition. La définition pourrait consister en une définition liée à la langue (propriétés grammaticales, déclinations) et / ou une définition de la langue de l'indépendance (description de la notion). P>

Un mot peut avoir plusieurs définitions (livre = (noun) matériau, = (verbe) utilisation de la localisation de la réserve). p>

Remarques strong> p>

Comme des mots simples sont traités, cela ne considère pas qu'un texte survenu est dans Général mono-lingual. Comme un texte peut être de langages mixtes, et je ne vois aucune surcharge spéciale dans la complexité O, qui semble sans importance. P>

Donc, une structure de données abstraite ultérieure serait la suivante: p>

import gnu.trove.map.*;

/**
 * Map of word to DefinitionEntry.
 * Key: word.
 * Value: offset in byte array wordDefinitionEntries,
 * 0 serves as null, which implies a dummy byte (data version?)
 * in the byte arrary at [0].
 */
TObjectIntMap<String> wordDefinitions = TObjectIntHashMap<String>();
byte[] wordDefinitionEntries = new byte[...]; // Actually read from file.

void walkEntries(String word) {
    int value = wordDefinitions.get(word);
    if (value == 0)
        return;
    DataInputStream in = new DataInputStream(
        new ByteArrayInputStream(wordDefinitionEntries));
    in.skipBytes(value);
    int entriesCount = in.readShort();
    for (int entryno = 0; entryno < entriesCount; ++entryno) {
        int language = in.readByte();
        walkDefinition(in, language); // Index to readUTF8 or gzipped bytes.
    }
}


11 commentaires

JOOP, le défi n'est que de 1) identifier rapidement quelle (s) langue (s) un mot est légal dans, et 2) renvoyer un ensemble de pointeur (s) à ces définitions. Supposons que vous commencez avec n dictionnaires individuels, comme Reta Vortaro. Je n'ai aucune application à l'esprit, je demande seulement d'esquisser comment cela pourrait être conceptuel. Pensez-y comme une question d'entrevue de style Google.


Exploiter stemming ( salut / salut / saluée / salutation / salutations / salutations ), l'entrée de Trie pour salue pourrait avoir un pointeur à un (spécifique à la langue) Objet STEMMER (dont nous recherchons les caractères restants et renvoie NULL ou un pointeur à une définition). Cela résout simultanément la compacité, la recherche. Mais pouvons-nous généraliser cela à une tige multilingue ...? Et comment gérer des mots non apparentés avec une tige commune, par ex. flamant / flamanto / flambé ?


En fait, depuis flambé est un mot de prêt du français, comment l'anglais Stetmmer pourrait-il simplement indiquer le mot français comme étant légal dans les deux langues?


Pour Flambé L'Anglais Stetemmer pourrait pointer vers le mot français (vous avez également besoin de A pour avoir une structure de définition neutre de la langue, sinon la définition de la définition pourrait contenir des listes de paires (langue, de définition))? Il y aura des mots de prêt universels tels que Pizza qui sont légaux dans la plupart du / toutes les N langues. Je suppose que la façon dont vous développez cela dépend en outre de ce qu'est un objet de définition (définition spécifique à la langue? Définition neutre de la langue? Liste de simile de thésaurus spécifique à la langue? ...)


à propos des stemmers. Prenez le néerlandais d'investissement ; Une tige anglaise chercherait investisseur et échouez plus loin.


Oui c'est un comportement correct. Voici un STEMMER néerlandais brut . Quelqu'un a déjà essayé des stemmers multilingues? (Google me montre des références à par exemple Xapian ) Quelles sont les deux langues la plus grande similarité pour stemming?


Boule de neige est une boîte à outils pour les stemmers de langue étrangère. Je remarque deux choses à ce sujet: a) semble avoir besoin de romainiser tous les caractères spéciaux b) une timmer ne peut renvoyer qu'un résultat de la scanne, donc pas de stemmers multilingues.


Vous ne pouvez faire que stemming une fois que vous connaissez la langue . Si vous ne connaissez pas la langue (encore), vous aurez à (au moins) reporter de reporter stemming.


Mais tout mon point est que vous pouvez simultanément faire une classification stemming et linguistique multilingue . (par exemple, Coveo fait )


@Joopeggen Savez-vous où je peux télécharger un dictionnaire espagnol - anglais similaire de ce qu'ils ont pour le chinois - anglais ( CC -cedict.org/wiki )


@Growler Désolé, mais au moins, ce sont des langues populaires. Bonne chance.




0
votes

J'ai eu une tâche similaire (mais pas exactement): implémenter une cartographie à quatre voies pour les ensembles, par exemple. A , b , c , d

chaque élément x a-t-il Projections dans tous les ensembles, XA , xb , xc , xd ;

La tâche a été la suivante: pour chaque élément rencontré, déterminez quel ensemble il appartient et trouvez ses projections dans d'autres ensembles.

Utilisation de langues Analogie: Pour n'importe quel mot, identifiez sa langue et trouvez toutes les traductions vers d'autres langues. < / p>

Toutefois: dans mon cas, un mot peut être identifié de manière unique comme appartenant à une seule langue, alors aucun faux ami, tel que Burro en espagnol, c'est l'âne en anglais, alors que Burro en italien est Beurre en anglais (voir aussi https://www.daytranslations.com/blog/diFferent-Manings / )

J'ai implémenté la solution suivante:

  • quatre cartes / dictionnaires correspondant à l'entrée de son identifiant unique (entier) XXX
  • Quatre cartes / dictionnaires correspondant à l'ID unique à la langue correspondante XXX

    pour chaque rencontre x , j'ai besoin de faire 4 recherches au pire pour obtenir son identifiant (chaque recherche est o (journal (n)) ) ; Ensuite 3 opérations d'accès, chaque O (journal (n)) . Tout dans tout, o (journal (n)) .

    Je n'ai pas implémenté cela, mais je ne vois pas pourquoi les ensembles de hachage ne peuvent pas être utilisés pour l'une ou l'autre des dictionnaires pour Faites-le O (1) .

    retour à votre problème: Compte tenu de n concepts en m langues (donc n * m mots au total)

    Mon approche s'adapte de la manière suivante:

    M Cherchez Hashsets, qui vous donnent une pièce d'identité entier pour chaque langue ( ou aucun / null si le mot n'existe pas dans la langue). L'étui superposé est couvert par le fait que les recherches pour différentes langues produiront différents identifiants.

    pour chaque mot, vous faites m * o (1) recherches dans les ensembles de hachages correspondant aux langues, cédant k <= m IDS, identifiant le mot comme appartenant à K langues K;

    pour chaque identifiant que vous devez faire (M-1) * O (1) Recherche dans des dictionnaires réels, mappage k IDS à M-1 Traductions chacune)

    au total, O (m k m) que je pense n'est pas mauvais, étant donné que votre m = 40 et k sera beaucoup plus petit que m dans la plupart des cas (k = 1 Pour beaucoup de mots).

    comme pour le stockage: N m mots + n m entiers pour les dictionnaires ID-TO-Word et le même montant pour les recherches inverse ( word-to-id);


2 commentaires

Je ne vois pas la pertinence de cela à ma question et votre principe "dans mon cas, un mot peut être identifié de manière unique comme appartenant à une langue que" est totalement artificiel et viole la question (donc < I> "ID entier unique à travers les langues" sort de la fenêtre immédiatement), mais de toute façon, vous n'avez pas répondu à quelle structure de données unique que vous utiliseriez pour gérer "burrro" (espagnol), "burrito" (les deux Espagnol & Anglais), 'Burrow' (Anglais), ... "Gardez N Hatassers / dictionnaires distincts, un pour chaque langue" violera les deux contraintes que j'ai données en étant extrêmement gaspillée à la mémoire de la mémoire et à la recherche.


(Ajout de clarification pour votre cas dans le corps de la poste)