Ταχυτερος αλγοριθμος ευρεσης πιθανων λεξεων

[Spect~]

Προσπαθω να ξεσκουριασω λιγο και κοιταω να φτιαξω μια εφαρμογουλα στην οποια θα δινω εγω καποια γραμματα και θα μου εμφανιζει ολες τις πιθανες λεξεις που μπορουν αυτα τα γραμματα να δημιουργησουν ψαχνοντας σε ενα αρχειο με λεξεις.

 

Παλαιοτερα που το ειχα κανει ο τροπος ηταν ο εξης.

 

Ειχα ενα δυσδιαστατο πινακα Α με τα γραμματα της αλφαβητου και διπλα 0 τιμη. Εψαχνα ενα ενα τα γραμματα που μου ειχα σαν εισοδο και καθε φορα που ταιριαζε εβαζα +1 στην τιμη του πινακα.

 

Στη συνεχεια εκανα το ιδιο πραγμα για καθε μια λεξη αλλα οταν ενα γραμμα της λεξης ταιριαζε με γραμμα απο τον πινακα Α τοτε εκανα -1 και στο τελος εαν ειχα αρνητικη τιμη στον πινακα ηξερα οτι αυτη η λεξη δεν μπορει να δημιουργηθει.

 

Τωρα αυτος ο τροπος μου φαινεται -και ειναι- αρκετα αργος και εχει αρκετους πλεονασμους οποτε λεω να το δω απο μια αλλη προσεγγιση. Αυτο που σκεφτομαι λοιπον ειναι

 

εχω τη λεξη Α σαν εισοδο και την λεξη Β που διαβαζω μια μια απο ενα αρχειο. 

Σκεφτηκα λοιπον ταξινομο τα γραμματα της εισοδο Α και τα γραμματα της λεξης Β και αρχιζω τον ελεγχο. Εαν φτασω στο τελευταιο γραμμα και εχω και σε αυτο match σημαινει οτι η λεξη μπορει να δημιουργηθει οποτε την βαζω σε ενα πινακα για να την εμφανισω αργοτερα. 

 

Καθε φορα θα μπορω να σταματαω οταν δω οτι εχω περασει καποιο γραμμα δηλαδη αν κοτιαω το γραμμα "ε" και το γραμμα μου ειναι πχ το "κ" να μην συνεχιζω γιατι δεν θα το βρω παρακατω.

 

Σε κατι που κολαω και ακομη δεν εχω σκεφτει ειναι αν με καποιο τροπο θα μπορω να σταματαω πριν φτασει το λεξικο στο τερμα ή θα πρεπει καθε φορα να ελεγχω ολες τις λεξεις.

 

Ακομη δεν εχω γραψει τιποτα και ειμαι σε θεωρητικο επιπεδο για αυτο δεν παραθετω κωδικα.

 

Καμια ιδεα ή καποιος αλλο γρηγοροτερος τροπος?

[zynif]

Δεν καταλάβα και πολλά διαβάζοντας το μήνυμα αλλά πιστεύω θες έναν αλγόριθμο που να σου φτιάχνει όλους τους δυνατούς συνδυασμούς (combinations) και όλες τις μεταθέσεις (permutation) καθενός συνδυασμού  . Οι συνδυασμοί είναι 2^n ενώ τα permuations n!.  Κάθε λέξη που βγάζεις θα την συγκρίνεις με το λεξικό που έχεις για να δεις εάν υπάρχει.

 

Tώρα μπορείς να κάπως να μειώσεις τον χρόνο πχ μάλλον δεν υπάρχουν ελληνικές λέξεις με τρία σύμφωνα στην σειρά

[Aztec]

Αν θέλεις να πας πραγματικά γρήγορα πρέπει να κάνεις preprocess ενα tree όπου το κάθε node θα έχει τα γράμματα με αλφαβητική σειρά (ACT) και στο ίδιο το node θα έχεις και όλες τις λέξεις που μπορεί να φτιάξει κάποιος με αυτα τα γράμματα  (CAT ...)

[Spect~]

εστω οτι εχω σαν εισοδο το  Π Τ Ι Σ Ι Α Κ Λ
θελω να μου εμφανισει τους πιθανουν συνδυασμους οπως ΣΠΙΤΙ, ΠΙΤΣΑ, ΚΑΤΙ κτλ.

 

εγω αυτο που σκεφτηκα μεχρι τωρα ειναι πχ το πρωτο το κανω Α Ι Ι Κ Λ Π Σ Τ
και οι λεξεις θα γινουν αντιστοιχα Ι Ι Π Σ Τ, Α Ι Π Σ Τ , Α Ι Κ Τ κτλ

 

αυτο που κανω εγω ειναι αφου τα εχω και τα δυο ταξινομημενο πλεον κοιταω λοιπον

για τη λεξη σπιτι για παραδειγμα 

 

Το Ι ειναι ιδιο με το Α οχι πηγαινε στο επομενο , Το Ι ειναι ιδιο με το Ι ναι πηγαινε στο επομενο και στις δυο λεξεις, το Ι ειναι ιδιο ναι πηγαινε στο επομενο και στις δυο λεξεις, το Π ειναι ιδιο με το Κ οχι πηγαινε στο επομενο μονο στην πρωτη λεξη κτλ.

 

Οταν δω καποιο γραμμα απο τη λεξη δεν υπαρχει στα γραμματα τις εισοδο οπως πχ αν ειχα τη λεξη Α Ζ Ι Ρ (ζαρι) οταν θα εβρισκε οτι το Κ ειναι πιο μεγαλο απο το Ζ τοτε να σταματησει να κοιταει αυτη τη λεξη και να παρει την επομενη γιατι δεν θα την βρει σιγουρα.

[Aztec]

εστω οτι εχω σαν εισοδο το  Π Τ Ι Σ Ι Α Κ Λ

θελω να μου εμφανισει τους πιθανουν συνδυασμους οπως ΣΠΙΤΙ, ΠΙΤΣΑ, ΚΑΤΙ κτλ.

 

εγω αυτο που σκεφτηκα μεχρι τωρα ειναι πχ το πρωτο το κανω Α Ι Ι Κ Λ Π Σ Τ

και οι λεξεις θα γινουν αντιστοιχα Ι Ι Π Σ Τ, Α Ι Π Σ Τ , Α Ι Κ Τ κτλ

 

αυτο που κανω εγω ειναι αφου τα εχω και τα δυο ταξινομημενο πλεον κοιταω λοιπον

για τη λεξη σπιτι για παραδειγμα 

 

Το Ι ειναι ιδιο με το Α οχι πηγαινε στο επομενο , Το Ι ειναι ιδιο με το Ι ναι πηγαινε στο επομενο και στις δυο λεξεις, το Ι ειναι ιδιο ναι πηγαινε στο επομενο και στις δυο λεξεις, το Π ειναι ιδιο με το Κ οχι πηγαινε στο επομενο μονο στην πρωτη λεξη κτλ.

 

Οταν δω καποιο γραμμα απο τη λεξη δεν υπαρχει στα γραμματα τις εισοδο οπως πχ αν ειχα τη λεξη Α Ζ Ι Ρ (ζαρι) οταν θα εβρισκε οτι το Κ ειναι πιο μεγαλο απο το Ζ τοτε να σταματησει να κοιταει αυτη τη λεξη και να παρει την επομενη γιατι δεν θα την βρει σιγουρα.

 

 

Αυτο θα το κανεις για καθε μια λεξη απο το λεξικο ? Δηλαδη αν εχεις 100.000 λεξεις θα κάνεις 100.000 sortings και 100.000+++++++  συγκρίσεις με τον τρόπο που ανέφερες ? σειριακά ανατρέχεις το λεξικό ?

[Spect~]

Ναι σειριακα!

 

για αυτο προσπαθω να βρω καποιο πιο γρηγορο τροπο

[zynif]

Τα binary search /hash map δεν είναι καλύτερα ;

[Aztec]

Τα binary search ή hash map δεν είναι καλύτερα ;

 

και το trie

[Spect~]

πως να το κανω δηλαδη?

[defacer]

Κάνεις πρώτα ένα στάδιο προεπεξεργασίας του λεξικού (αυτό μπορεί να γίνει μια φορά και μετά να διαβάζεις το έτοιμο αποτέλεσμα όποτε θέλεις):

 

1. Παίρνεις κάθε λέξη και βάζεις τα γράμματα σε αλφαβητική σειρά.

 

2. Ταξινομείς τα αποτελέσματα και αντιστοιχείς το καθένα με τις λέξεις που έχουν τα ίδια γράμματα, π.χ.

 

ΑΙΠΠ => ΠΑΠΙ ΠΙΠΑ

 

Αυτό μπορείς να το κάνεις και σε ένα απλό text file.

 

3. Αυτό το text file όταν έρθει η ώρα να το ψάξεις θα το βάλεις μέσα σε κάποιο key/value data structure που είναι sorted στα keys, δεν έχει τόσο πολλή σημασία ποιό ακριβώς και δε θα μπω σε λεπτομέρειες. H πιο απλή περίπτωση θα ήταν να βάλεις π.χ. τα keys σε ένα πίνακα στον οποίο θα κάνεις binary search για να βρεις αν το τάδε key υπάρχει.

 

Τώρα το πρόβλημα έχει αναχθεί στο εξής: δεδομένου ενός συνόλου αλφαβητικά ταξινομημένων γραμμάτων, βρες ποιά από τα (επίσης ταξινομημένα) υποσύνολά του αντιστοιχούν σε υπαρκτά keys.

 

Εφόσον για κάθε ένα υποσύνολο είναι πανεύκολο να δεις αν υπάρχει το key το πρόβλημα τώρα ανάγεται στο εξής: δεδομένου ενός συνόλου αλφαβητικά ταξινομημένων γραμμάτων, δημιούργησε μια λίστα με τα ταξινομημένα υποσύνολα. Αυτό είναι το πρόβλημα του πώς να υπολογίσεις το power set του αρχικού σου συνόλου.

 

Π.χ. για την είσοδο Α Ι Π Π το power set είναι

 

(κενό σύνολο)

Α

Ι

Π

Π (2η φορά)

Α Ι

Α Π

Α Π (2η φορά)

Ι Π

Ι Π (2η φορά)

Π Π

Α Ι Π

Α Ι Π (2η φορά)

Α Π Π

Ι Π Π

Α Ι Π Π

 

Γενικά το power set θα αποτελείται από 2^Ν υποσύνολα συμπεριλαμβανομένων των διπλών, -1 γιατί το κενό σύνολο δε σ' ενδιαφέρει. Το 2^Ν δεν είναι και πολύ καλό αλλά δεδομένου ότι για π.χ. 16 γράμματα στην είσοδο (που είναι πολλά) η δουλειά που θα έχεις να κάνεις θα γίνει dominate από τις το πολύ 65535 binary search που θα χρειαστούν, στην πράξη θα είναι στιγμιαία η λύση.

 

Μ' αυτά τώρα ξέρεις όλα όσα χρειάζεται για να λύσεις το πρόβλημα με λογικά γρήγορο τρόπο.

 

Βελτιώσεις υπάρχουν αν έχεις όρεξη, αλλά πρώτα κάντο να δουλέψει.

[Spect~]

θα το κοιταξω απο το πρωι με καθαρο μυαλο!! ευχαριστω!

[Spect~]

@defacer 

 

σκεφτομουν οτι ενα αρχικο προβλημα στο τροπο σου ειανι το πως θα δημιουργησω αυτο το αρχειο οταν μιλαμε για 100.000 λεξεις. χειροκινητα δεν παιζει. Καμια ιδεα? Εκτος αν μετα παμε σε νεα εφαρμογη για να κανει αυτο το πραγμα

[albNik]

Γενικά το power set θα αποτελείται από 2^Ν υποσύνολα συμπεριλαμβανομένων των διπλών

Ισχυει οταν δεν εχεις διπλες π.χ. a b c d ειναι (1+1)(1+1)(1+1)(1+1)=2^4

αν εχεις επαναλήψεις π.χ.  aaa bb c dd το power-set ειναι (3+1)(2+1)(1+1)(2+1) 

[defacer]

Εκτος αν μετα παμε σε νεα εφαρμογη για να κανει αυτο το πραγμα

 

Εννοείται αυτό. 

 

Αλλά εντάξει τώρα "εφαρμογή", μιλάμε για 5 λεπτά σε οποιαδήποτε γλώσσα προγραμματισμού ξέρεις που δεν είναι C. 

[Spect~]

Χαιρετω!! Λοιπον @Defacer επειδη ο αλγοριθμος σου θελει προεργασια και ψαξιμο τον αφηασα στην ακρη και υλοποιησα την αρχικη μου σκεψη με ικανοποιητικα αποτελεσματα!  (και ειναι και πιο ευκολα προσαρμοσιμο σε αλλες γλωσσες)

 

Αυτο που θελω να μαθω τωρα για να μην ανοιξω νεο θεμα ειναι το εξης!

 

Εχω μια λιστα με ενα custom Array Adapter

 

Το Listview εχει δυο String

 

public ListViewItem(String word, String points) {
        this.word = word;
        this.points= points;
    }

 

πριν εμφανισω την λιστα θελω να της κανω μια ταξινομηση με βαση τους ποντους.

 

Εδω καπου το εχασα! Ειναι και το κεφαλι μου λιγο καζανι δεν ηθελα πολυ! Καμια ιδεα!?

 

Ειδα για Comparator αλλα δεν καταλαβα τιποτα!! ΚΑμια βοηθεια?

 

EDIT

 

εβγαλα ακρη σε ενα βαθμο! Κανει ταξινομηση αλλα το προβλημα ειναι οτι ταξινομοι τους μονοψηιους απο το μεγαλυτερο στο μικροτερο και μετα τους διψηφιους το ιδιο δηλαδη

 

9

9

8

3

1

14

12

10

 

εδιτ ξανα! το λυσα ! μετετρεψα τις τιμες σε ιντ και το εκανα σαν αυτο

 

if (this.age < other.age) return 1;
else if (this.age == other.age) return 0;
else return -1;