[Tutti] Contest: T9 lookalike

[gugoXX]

Si vuole costruire una delle parti "Core" di un HID (Human Interface Device) che utilizza il T9
il concetto del T9 e' che, avendo una tastiera con pochi tasti, si vuole offrire all'utente la possibilita' di comporre in modo semplice tutte le parole possibili.

I tasti in questione sono 9 (in realta' per il nostro esercizio sono solo 8)
Con la seguente associazione statica e data a priori.
1 -> Nulla
2 -> abc
3 -> def
4 -> ghi
5 -> jkl
6 -> mno
7 -> prqs
8 -> tuv
9 -> wxyz

Si ha a dispozione un dizionario di parole dato, con tante parole, alcune corte, alcune lunghe, alcune lunghissime.
Lunghezza indefinita, ma volendo anche piu' lunghe di 50 caratteri, dato che si vuole a priori supportare anche lingue come il tedesco, con lunghezza indefinita delle parole, e magari anche qualche applicazione crittografica, dove le password possono appunto anche essere indefinitamente lunghe.

Si ottiene in ingresso un numero, es:
2426
Scopo dell'esercizio e' quello di restituire in output tutte le parole del nostro dizionario che possono essere ricondotte al numero in questione.
Supponendo in ingresso un dizionario/enciclopedia italiano, un output probabile potra' essere:
bico
ciao
cibo
cico

In modo ovviemente veloce, ovvero con possibilmente un algoritmo ottimale o quasi.
La soluzione deve essere semplicemente scalabile, nel senso che all'aumentare del numero di parole del dizionario la ricerca dell'output non deve peggiorare (troppo).
Un assunto che si puo' fare, ma che non deve essere vincolante, e' che ad un numero composto da tante cifre e' probabile che corrispondano meno parole reali, e viceversa, ma non e' detto che siano comunque per forza una sola.

Qui l'elenco delle parole italiane da supportare. Come detto, la lunghezza di una parola potrebbe essere a priori anche molto lunga.
http://www.yorku.ca/lbianchi/italian.../italia-1a.zip
Aprite, leggete, capite e parsate come vi pare.

Presto arrivera' anche l'elenco dei valori numerici target di cui poi trovare le corrispondenze.

[ndakota]

Bello

[Tommo]

Aggiungerei anche che visto l'obiettivo del programma, non bisogna ottimizzare il caso della ricerca di "2426" ma più che altro la ricerca del nuovo gruppo dato il vecchio gruppo e la nuova cifra

[Ryuzaki_Eru]

Questo è interessante

[shinya]

Ho tirato fuori questa schifezza in C++... però è limitato, perchè non tira fuori match parziali (bico, cico, nell'esempio) ma solo match completi.
Spero di vedere soluzioni più furbe della mia

edit: è un pò "convoluted", ma adesso dovrebbe stampare anche i match parziali...
Continuo a sperare in soluzioni migliori

martind@b0x:~/src/random/contest-t9$ cat > t9.cpp 
#include <iostream>
#include <algorithm>
#include <iterator>
#include <map>
#include <string>
#include <fstream>
#include <sstream>
#include <set>

inline std::string int_to_string(int n) {
  std::stringstream ss;
  ss << n;
  return ss.str();
}

struct t9bot {
  std::map<char, std::string> keyboard;
  std::multimap<std::string, std::string> candidates;

  t9bot() {
    const std::string chars[] = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    for (int i = 0; i < 8; ++i)
      for (size_t j = 0; j < chars[i].length(); ++j)
        keyboard[chars[i][j]] = int_to_string(i+2);
  }

  inline void operator()(const std::string word) {
    std::string key;
    for (size_t i = 0; i < word.length(); ++i) key += keyboard[word[i]];
    candidates.insert(std::pair<std::string, std::string>(key, word));
  }

  void print_solutions(const std::string key) {
    typedef std::multimap<std::string, std::string>::iterator map_iterator;
    map_iterator low = candidates.lower_bound(key);
    map_iterator high = candidates.upper_bound(key+"9");
    std::set<std::string> solution_set;
    for (map_iterator it = low; it != high; ++it)
      solution_set.insert(it->second.substr(0, key.length()));
    for (std::set<std::string>::iterator it = solution_set.begin();
        it != solution_set.end(); ++it)
      std::cout << *it << std::endl;
  }
};

int main(int argc, char **argv) {
  t9bot bot;
  std::ifstream dictionary(argc > 1 ? argv[1] : "dictionary");
  bot = std::for_each(
          std::istream_iterator<std::string>(dictionary),
          std::istream_iterator<std::string>(), bot);

  while (std::cin.good()) {
    std::string test;
    std::cin >> test;
    if (!test.empty()) bot.print_solutions(test); 
  } 

  return 0;
}
martind@b0x:~/src/random/contest-t9$ g++ -Wall -O2 t9.cpp -o t9
martind@b0x:~/src/random/contest-t9$ echo 2426 | ./t9 dict
agam
bian
bico
cham
chan
ciam
cian
ciao
cibo
cico
martind@b0x:~/src/random/contest-t9$

[fero86]

propongo un'idea per migliorare la versione che fa solo match completi: partendo dal dizionario é possibile creare una hash table dove le chiavi sono le sequenze numeriche necessarie per comporre le parole e i valori sono le liste delle parole che possono essere composte con una certa sequenza numerica; per esempio in questa hash table alla chiave 2426 sará contenuta una lista di due elementi, "cibo" e "ciao".

se N é il numero di parole del dizionario il tempo necessario per costruire questa hash table é O(N) e lo spazio anche (quindi, in particolare, lo spazio occupato resta asintoticamente identico). i vantaggi sono evidenti perché la hash table la si costruisce una volta per tutte e poi quando la si ha si puó fare qualunque consultazione in tempo costante, ottenendo grande efficienza anche nel caso in cui le cifre arrivino sul momento.

per completare l'idea non resta che pensare a un modo conveniente per memorizzare questa struttura dati in un file oltre che in memoria.

purtroppo é solo un'idea e non so se avró il tempo di realizzarla T_T

[Tommo]

Lo stavo facendo ma poi m'è arrivata la licenza apple

Cmq stavo provando a realizzare un albero dove il nodo al N-esimo livello è la parola all'N-esima posizione.

[fero86]

Originariamente inviato da Tommo

Cmq stavo provando a realizzare un albero dove il nodo al N-esimo livello è la parola all'N-esima posizione.

gli alberi in genere non contengono mica un solo nodo per livello... e comunque giá std::map é implementata tramite BST.

[Ryuzaki_Eru]

Originariamente inviato da Tommo

Lo stavo facendo ma poi m'è arrivata la licenza apple

What?

[DanieleC88]

Conta solo il tempo di ricerca o anche il tempo di caricamento?

EDIT: e lo 0 lo possiamo ignorare?
EDIT: in più ci sono parole come "abat-jour" che non sono esclusivamente alfabetiche, le ignoriamo?

[Rikiji]

Lento a caricare ma veloce nella ricerca (più che altro veloce da scrivere )

dic=Hash.new

h=Hash.new
('a'..'r').inject(6) {|i,c| h[c.to_sym] = (i/3).to_i; i+=1;}
('s'..'y').inject(23) {|i,c| h[c.to_sym] = (i/3).to_i; i+=1;}
h[:z] = 9
#p h.inspect

File.open("merged.dic") do |f|
  while line = f.gets
    line.strip!
    s = ""
    line.split('').each do |c|
      s+= h[c.to_sym].to_s
      end

    dic[s] ||= Array.new
    dic[s] << line    
  end
  # p dic.inspect
end

dic["2426"].each do |word|
  puts word
end

dic["2777682666"].each do |word|
  puts word
end

[Tommo]

Originariamente inviato da fero86

gli alberi in genere non contengono mica un solo nodo per livello... e comunque giá std::map é implementata tramite BST.

Stavo facendo un albero che per ogni livello contiene al più 26 sottoalberi, uno per ogni lettera dell'alfabeto.
Quindi se scrivi "2" lui ti ritorna i sottoalberi A, B e C e scrive a, b o c.
Quando poi scrivi "4" lui ritorna tutti i sottoalberi di A B C di senso compiuto (cioè, che non sono null) tra AG, AH, AI, BG, BH, BI, CG, CH, CI.

Una volta che la ricerca è terminata si ha un insieme di nodi; percorrendo i nodi verso l'alto si ottengono tutte le parole (anche incomplete) cercate.
In questo modo tra l'altro è possibile dare diversi pesi alle diverse parole, assegnando un peso ai nodi che compongono la parola...

[banryu79]

Originariamente inviato da Rikiji

Lento a caricare ma veloce nella ricerca (più che altro veloce da scrivere )

Scusa, in che linguaggio è scritto? Non l'ho riconosciuto, sarà che stanotte ho dormito poco poco e adesso sono piegato

@Tommo: bella l'idea dell'albero, ci avevo pensato anche io ieri, in parte proprio per il problema della distinzione tra parole formate/parole incomplete...

[shinya]

Originariamente inviato da banryu79

Scusa, in che linguaggio è scritto? Non l'ho riconosciuto, sarà che stanotte ho dormito poco poco e adesso sono piegato

ruby, direi...

Comunque sono curioso di vedere una soluzione basta sull'idea postata da Tommo... avevo anch'io in mente qualcosa di simile ma non ci sono arrivato, e quindi ho ripiegato su una soluzione più barbara

[cionci]

Originariamente inviato da Tommo

Stavo facendo un albero che per ogni livello contiene al più 26 sottoalberi, uno per ogni lettera dell'alfabeto.
Quindi se scrivi "2" lui ti ritorna i sottoalberi A, B e C e scrive a, b o c.
Quando poi scrivi "4" lui ritorna tutti i sottoalberi di A B C di senso compiuto (cioè, che non sono null) tra AG, AH, AI, BG, BH, BI, CG, CH, CI.

Una volta che la ricerca è terminata si ha un insieme di nodi; percorrendo i nodi verso l'alto si ottengono tutte le parole (anche incomplete) cercate.
In questo modo tra l'altro è possibile dare diversi pesi alle diverse parole, assegnando un peso ai nodi che compongono la parola...

Quanto è grande un albero del genere che arriva fino a 50 di profondità ? 26^50 = 2^235 bit puntatori...ovvero è una soluzione improponibile

[marco.r]

Originariamente inviato da cionci

Quanto è grande un albero del genere che arriva fino a 50 di profondità ? 26^50 = 2^235 bit puntatori...ovvero è una soluzione improponibile

ma l'albero non e' completo, e contiene poche parole di quella lunghezza, per cui potrebbe essere fattibile. In ogni caso ci sono strutture dati apposite per questo scopo.

[shinya]

Originariamente inviato da fero86

propongo un'idea per migliorare la versione che fa solo match completi: partendo dal dizionario é possibile creare una hash table dove le chiavi sono le sequenze numeriche necessarie per comporre le parole e i valori sono le liste delle parole che possono essere composte con una certa sequenza numerica; per esempio in questa hash table alla chiave 2426 sará contenuta una lista di due elementi, "cibo" e "ciao".

Si è quello che fa il mio programma. Sta tutto nella multimap.

[wizard1993]

posto la mia soluzione in java.
ho usato una metodologia simile a quella proposta da Tommo (è stata la prima cosa a cui ho pensato), solo invece di puntatori ho usato delle mappe.
Come diceva Cionci effettivamente usa una vagonata di memoria:
usando hashMap con fattore di caricamento 0.75 ho picchi di 300 mb di ram , usando mappe basate su alberi ne uso 200.
sul mio sistema la soluzione è elaborata (caricamento incluso) in 9 secondi

wizard1993@wizard1993-desktop:~/NetBeansProjects/t9/dist$ time java -jar t9.jar 
[agam]
[bian]
[bico]
[cham]
[chan]
[ciam]
[cian]
[ciao]
[cibo]
[cico]

real	0m8.239s
user	0m9.621s
sys	0m0.420s

e il sorgente

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package t9;
import java.io.*;
import java.util.*;

/**
 *
 * @author wizard1993
 */
public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws FileNotFoundException{
        new T9Treee().search("2426");
        //System.in.read();
    }
}

class T9Treee {

    node root = new node("");
    final String symbols = "ABCDEFGHIJKLMNOPQRDQSTUVWXYZ";
    HashMap<Integer, String> reverse = new HashMap<Integer, String>();

    private void initTree() {
        /*2 -> abc
        3 -> def
        4 -> ghi
        5 -> jkl
        6 -> mno
        7 -> prqs
        8 -> tuv
        9 -> wxyz*/

        for (int i = 0; i < symbols.length(); i++) {
            String string = symbols.charAt(i) + "";
            node n = new node(string);
            root.nextNodes.put(string, n);
        }
        reverse.put(2, "abc");
        reverse.put(3, "def");
        reverse.put(4, "ghi");
        reverse.put(5, "jkl");
        reverse.put(6, "mno");
        reverse.put(7, "pqrs");
        reverse.put(8, "tuv");
        reverse.put(9, "wxyz");




    }

    private void parse() throws FileNotFoundException {
        for (int i = 0; i < symbols.length(); i++) {
            String fileName = "ITALIANO." + symbols.charAt(i);
            Scanner input = new Scanner(new BufferedInputStream(new FileInputStream(fileName)));
            while (input.hasNext()) {
                String string = input.nextLine();
                insert(string);
            }
            input.close();
        }
    }

    private void insert(String string) {
        node n = root;
        String swap = "";
        for (int i = 0; i < string.length(); i++) {
            String c = string.charAt(i) + "";
            swap += c;
            node next = n.nextNodes.get(c);
            if (next == null) {
                next = new node(c);
            }
            n.nextNodes.put(c, next);
            next.words.add(swap);
            n = next;
        }
    }

    private class node {

        String character;

        public node(String character) {
            this.character = character;
        }
        TreeMap<String, node> nextNodes = new TreeMap<String, T9Treee.node>();
        Set<String> words = new TreeSet<String>();
    }

    public T9Treee() throws FileNotFoundException {
        initTree();
        parse();
    }

    public void search(String seq, node n, int depth) {
        if(n==null)return;
        if (depth >= seq.length() && n != null) {
            System.out.println(n.words);
            return;
        }
        String possible = reverse.get(Integer.valueOf(seq.charAt(depth) + ""));
        for (int i = 0; i < possible.length(); i++) {
            String c = possible.charAt(i) + "";
            search(seq, n.nextNodes.get(c), depth+1);
        }


    }
    public void search(String s){
        search(s, root, 0);
    }
}

[cionci]

Originariamente inviato da marco.r

ma l'albero non e' completo, e contiene poche parole di quella lunghezza, per cui potrebbe essere fattibile. In ogni caso ci sono strutture dati apposite per questo scopo.

Però se l'albero contiene le lettere 'a' e 'z' sei costretto a creare tutti i nodi null nel mezzo, con ovvio spreco di spazio
Senza considerare che una indicizzazione completa non è necessaria.

[ratman511]

in che senso contiene nodi null nel mezzo?hanno detto che l'albero è composto da 26 sottoalberi e quindi le lettere dovrebbero esserci tutte.e l'indicizzazione completa perchè non è necessaria?