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

[defacer]

Ε... προεργασία και ψάξιμο...

 

 

C#

var sourceUrl = "https://en.wiktionary.org/wiki/Appendix:Greek_word_lists/1";
var outFile = "f:\\wordmap";
    
using (var client = new WebClient())
{
    var html = client.DownloadString(sourceUrl);
    var xdoc = XDocument.Parse(html);
    
    var wordlist = xdoc.Root
        .XPathSelectElements("//div[@id='mw-content-text']/ul/li/a")
        .Select(x => Encoding.UTF8.GetString(Encoding.Default.GetBytes(x.Value)).ToUpper());
        
    var wordmap = wordlist
        .Select(s => s.Normalize(NormalizationForm.FormD).ToCharArray().Where(c => CharUnicodeInfo.GetUnicodeCategory(c) != UnicodeCategory.NonSpacingMark))
        .ToLookup(a => string.Concat(a.OrderBy(c => c)), string.Concat);
 
 
    File.WriteAllLines(
        outFile,
        wordmap
            .OrderBy(g => g.Key)
            .Select(g => string.Format("{0} => {1}", g.Key, string.Join(" ", g.Distinct())))

    );
}

Δεν είμαι σίγουρος τι imports χρειάζεται γιατί το έγραψα στο LINQpad. Με μια γρήγορη ματιά θέλει System.Linq, System.Net, System.Text, System.Xml.Linq.

 

 

 

Η άχρηστη γνώση της ημέρας: από αυτές τις υποτιθέμενες 10000 πιο συχνές ελληνικές λέξεις βγαίνει αρχείο με ~9250 γραμμές. Δηλαδή 17.5% απ' αυτές είναι αναγραμματισμοί άλλων.

 

Το ρεκόρ περισσότερων αναγραμματισμών (4) το έχει η εξής ομάδα (είναι η μόνη στα 4):

 

ΑΙΛΟΠ => ΠΑΛΙΟ ΠΛΟΙΑ ΛΟΙΠΑ ΑΠΛΟΙ

 

Η μεγαλύτερη λέξη της οποίας τα γράμματα βρίσκονται σε απόλυτη αλφαβητική σειρά είναι ΑΓΓΕΛΟΣ.

 

 

[Spect~]

Νεα ερωτηση γιατι εχω καει!

 

θελω σε ενα fragment που εχω κατι τιμες οταν αλλαξω fragment και αργοτερα επιστρεψω ξανα στο ιδιο να εμφανισω τις τιμες που ειχε πριν!

 

Με λιγο ψαξιμο ειδα οτι πρεπει να το σωσο πριν αλλαξω fragment και να τα περασω ξανα οταν επανελθω. οποτε και εκανα το εξης

 

 

 

εδω αποθηκευω τις τιμες κατα την αλλαγη 
    public void onSaveInstanceState(Bundle savedInstanceState) {
        super.onSaveInstanceState(savedInstanceState);
        savedInstanceState.putString("pl1", playerName1.getText().toString());
        savedInstanceState.putString("pl2", playerName2.getText().toString());      
    }
 
και ετσι τις επαναφερω
 
@Override
    public void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        if ((savedInstanceState != null)) {
            playerName1.setText(savedInstanceState.getString("pl1"));
            playerName2.setText(savedInstanceState.getString("pl2"));
        }
    }

 

την επαναφορα δοκιμασα να την κανω και στην onCreateView αλλα ματαια. Καμια ιδεα/λυση για το τι πρεπει να κανω?

[Spect~]

update!

 

με καθαροτερο κεφαλι ειδα οτι η onSaveInstanceState καλειτε οταν κλεισει η MainAcitivity που διαχειριζεται τα fragments. 

Οταν βγηκα απο την εφαρμογη με το home button και επεστρεψα ηταν οπως το αφησα. οταν αλλαζω fragments δεν καλειται οποτε και δεν αποθηκευει τιποτα. τωρα μενει να βρω μια αλλη λυση!

[Spect~]

την ανεβασα εδω και λιγες μερες! την συγκρινα σε μεγαλη γραμματοσειρα με την αλλη που ειχε κανει ενας γνωστος και απλα καμια σχεση η ταχυτητα!

 

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

 

https://play.google.com/store/apps/details?id=gr.stef.scrabblewordfinder

 

και αυτη του φιλου μου

https://play.google.com/store/apps/details?id=com.kasiarakos.greekwordfinder

[stavrosyomafias]

Βλέποντας κάτι εκπομπές που παίζουν μετά τα μεσάνυχτα, και περιέχουν λέξεις με αναγραμματισμό, σκέφτηκα να φτιάξω κάτι παρόμοιο, με την ιδέα του OP, (ίσως και ίδιο απ' ότι κατάλαβα), φυσικά δεν πρόκειται να το χρησιμοποιήσω για βρίσκω τις λέξεις από εκπομπές, αλλά το σκέφτηκα σαν καλή ιδέα να πειραματιστώ λίγο (και με τους αλγορίθμους αναζήτησης). C, είναι η γλώσσα που θα το υλοποιήσω. έχω ήδη σκεφτεί πάνω κάτω τον αλγόριθμο (μάλλον δυαδικό δένδρο).

Λοιπόν, το μόνο που χρειάζομαι, είναι κάποιο ελληνικό dictionary σε μορφή ".txt", έχετε τίποτα να προτείνεται?

[pmav99]

Μετά από 30 sec googling βρήκα αυτό: https://raw.githubusercontent.com/titoBouzout/Dictionaries/master/Greek.dic

[stavrosyomafias]

Μετά από 30 sec googling βρήκα αυτό: https://raw.githubusercontent.com/titoBouzout/Dictionaries/master/Greek.dic

Thanks, εγώ στο google, βρήκα κάτι περίεργα wordlist, του τύπου, που περιείχαν ονόματά, και ονόματα με περίεργους συνδυασμούς (π.χ. Nikos, N1k0s, κλπ), πράγμα που δεν το ήθελα, anyway σε ευχαριστώ και πάλι..

[DeltaLover]

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

 

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

 

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

 

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

 

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

 

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

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

 

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

 

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

 

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

 

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

 

 

 

Δες τον παρακάτω κώδικά σε python:

import itertools
# -*- coding: utf-8 -*-

class Anagramer(object):
  """Used to detect anagrams of Greek words."""

  _DICT_FILENAME = 'Greek.dic'

  def __init__(self, dict_filename=None):
    """Initializes the object preparing it for anagram searches."""
    self._letter_values = self._MakeLetterValues()
    self._dict_filename = dict_filename if dict_filename else self._DICT_FILENAME
    self._words = self._LoadWords()

  def FindAnagrams(self, selected_letters):
    """Finds all the possible anagrams that can be generated by the selected
    letters.
    """
    anagrams = []
    for combo in self._GetAllCombos(selected_letters):
      product = self._WordProduct(combo)
      if product in self._words:
        anagrams.extend(self._words[product])
    return anagrams

  def _GetAllCombos(self, selected_letters):
    """Returns all the combinations that can be formed by selected_letters."""

    if not selected_letters:
      return []
    combos = []
    for c in itertools.combinations(selected_letters, len(selected_letters)):
      combos.append(''.join(c))
    return combos + self._GetAllCombos(selected_letters[0:-2])

  def _MakeLetterValues(self):
    """Initializes the mapping of every Greek letter to a prime."""

    letters = (
      '''αβγδεζηθικλμνξοπρστυφχψωά   έ ή ί     ό    ύ   ώ'''
      '''ΑΒΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩΆ   Έ Ή Ί     Ό    Ύ   Ώ'''
    ).decode('utf-8')

    values = [
       2,  3,  5,  7, 11, 13, 17, 19, 23, 29, 31, 37,
      41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89
    ] * 4

    letter_values = {
     letter: value for letter, value in zip(letters, values) if letter.strip()
    }

    special_mappings = [
      ('ς', 'σ'),
      ('ϊ', 'ι'),
      ('ΐ', 'ι'),
      ('ΰ', 'υ'),
      ('ϋ', 'υ'),
    ]

    for c1, c2 in special_mappings:
      letter_values[c1.decode('utf-8')] = letter_values[c2.decode('utf-8')]

    letter_values[','] = 1
    return letter_values

  def _WordProduct(self, word):
    """Returns the product of all the letters in word."""

    p = 1
    for c in word.decode('utf-8'):
      p *= self._letter_values.get(c, 1)
    return p

  def _LoadWords(self):
    """Preloads the words from the dictionary."""

    words = {}
    for word in open(self._dict_filename):
      word = word.strip()
      product = self._WordProduct(word)
      if product not in words:
        words[product] = [word]
      else:
        words[product].append(word)
    return words

def Main():
  """Promts the user for letters and prints the anagrams."""

  a = Anagramer()
  while True:
    letters = raw_input('Enter the letters:')
    letters = letters.replace(' ', '')
    if not letters:
      break
    for w in a.FindAnagrams(letters):
        print w.decode('utf-8')

if __name__ == '__main__':
  Main()

Επεξ/σία 2 Ιουλίου 2016 από DeltaLover

[DeltaLover]

Ε... προεργασία και ψάξιμο...

 

 

C#

var sourceUrl = "https://en.wiktionary.org/wiki/Appendix:Greek_word_lists/1";
var outFile = "f:\\wordmap";
    
using (var client = new WebClient())
{
    var html = client.DownloadString(sourceUrl);
    var xdoc = XDocument.Parse(html);
    
    var wordlist = xdoc.Root
        .XPathSelectElements("//div[@id='mw-content-text']/ul/li/a")
        .Select(x => Encoding.UTF8.GetString(Encoding.Default.GetBytes(x.Value)).ToUpper());
        
    var wordmap = wordlist
        .Select(s => s.Normalize(NormalizationForm.FormD).ToCharArray().Where(c => CharUnicodeInfo.GetUnicodeCategory(c) != UnicodeCategory.NonSpacingMark))
        .ToLookup(a => string.Concat(a.OrderBy(c => c)), string.Concat);
 
 
    File.WriteAllLines(
        outFile,
        wordmap
            .OrderBy(g => g.Key)
            .Select(g => string.Format("{0} => {1}", g.Key, string.Join(" ", g.Distinct())))

    );
}

Δεν είμαι σίγουρος τι imports χρειάζεται γιατί το έγραψα στο LINQpad. Με μια γρήγορη ματιά θέλει System.Linq, System.Net, System.Text, System.Xml.Linq.

 

 

 

Η άχρηστη γνώση της ημέρας: από αυτές τις υποτιθέμενες 10000 πιο συχνές ελληνικές λέξεις βγαίνει αρχείο με ~9250 γραμμές. Δηλαδή 17.5% απ' αυτές είναι αναγραμματισμοί άλλων.

 

Το ρεκόρ περισσότερων αναγραμματισμών (4) το έχει η εξής ομάδα (είναι η μόνη στα 4):

 

ΑΙΛΟΠ => ΠΑΛΙΟ ΠΛΟΙΑ ΛΟΙΠΑ ΑΠΛΟΙ

 

Η μεγαλύτερη λέξη της οποίας τα γράμματα βρίσκονται σε απόλυτη αλφαβητική σειρά είναι ΑΓΓΕΛΟΣ.

 

 

 

 

Οσον αφορα ρεκορ αναγραμματισμων στο Greek.dic:

 

13 Αρίστου αρίστου άριστου άρτιους αστριού αστρίου ιατρούς ουρίτσα σάτυροι σταριού σταυροί ταύροις τουρσιά

12 ακίνητος ακονιστή ακόνιστη ακόντιση ανίκητος ανοικτής ατονικής ικανότης κονιαστή νατοϊκής Τηνιακός τηνιακός

11 άσυλο αυλός Αύλος άυλος λαούς λάσου λούσα σαλού σάλου Σαούλ ύαλος

11 άσπροι όσπρια Πάριος πάριος Πισαρό Πισάρο πόρισα σαπροί σπάροι σποριά σπόρια

11 άκρος Κάρος κάρος κόρας Όσκαρ όσκαρ ράκος ροκάς ρόκας Σαρκό σκάρο

11 άρτους άστρου σάτυρο σούρτα Σταυρό σταυρό Σταύρο ταρσού ταύρος τουράς τσάρου

11 άρτος Άστορ άστρο όρτσα ρόστα ρότας Σαρότ Σάρτο Ταρσό ταρσό τσάρο

11 άκριτους αστρικού Καστριού σατυρικό σκουτάρι Σκούταρι σταυρικό ταρσικού Τουρκιάς Τουρκίας τσαρικού

[Επισκέπτης]

Φόρτωσα το λεξικό που βρήκε ο pmvav99 σε μια λίστα κι από εκεί ο αλγόριθμος έχει ως εξής:

List<string> wordsList = new List<string>();        // περιέχει το λεξικό
List<string> foundWords = new List<string>();
string source = "ΠΤΙΣΙΑΚΛ";

// πρώτα βρίσκω λέξεις που έχουν κοινά γράμματα
Parallel.ForEach(wordsList, (word) => {
    bool flag = true;
    foreach (char c in word) {
        if (!source.Contains(c.ToString())) {
            flag = false;
            break;
        }
    }
    if (flag) {
        foundWords.Add(word);
    }
});

// για κάθε λέξη που έχει κοινά γράμματα, μετράω πόσες φορές υπάρχει κάθε γράμμα
List<string> finalWords = new List<string>();
Parallel.ForEach(foundWords, (word) => {
    bool flag = true;
    foreach (char c in word) {
        int letterTarget = word.Count(x => x == c);
        int letterSource = source.Count(x => x == c);
        if (letterTarget > letterSource) {
            flag = false;
            break;
        }
    }
    if (flag) {
        finalWords.Add(word);
    }
});

foreach (string word in finalWords) {
    Console.WriteLine(word);
}

Για 570.000 λέξεις που είναι στο λεξικό κάνει λιγότερο από ένα δευτερόλεπτο να βρει matches, συμπεριλαμβανομένου και του χρόνου που απαιτείται να φορτώσει το λεξικό.

 

Για τη λέξη που χρησιμοποιείς ως reference στο παράδειγμα σου, βρήκε τα παρακάτω matches:

ΑΠΙΛ, ΙΚΑ, ΙΚΤΙΣ, ΙΛΙΑ, ΙΛΙΑ, ΙΛΙΑΣ, ΙΣΑ, ΙΣΙΑ, ΙΣΚΑ, ΙΣΤΙΑ, ΙΤΙΑ, ΙΤΙΑΣ, ΚΑΙ, ΚΑΙΣ, ΑΣΚΙ, ΑΤΙ, ΚΑΛΤ, ΚΑΣΤ, ΚΑΤ, ΑΚΤΙΣ, ΛΑΙΤ, ΠΤΙΛΑ, ΑΛΙ, ΑΛΤ, ΣΑΙ, ΣΑΚΙ, ΣΑΛΙ, ΣΙΑ, ΣΙΑΤΛ, ΣΙΚΑ, ΣΙΛΑ, ΣΙΤΙ, ΣΙΤΙΚΑ, ΣΚΑΛΙ, ΣΚΙ, ΣΚΙΑ, ΣΛΙΠ, ΣΛΙΠΑΚΙ, ΣΠΙΚ, ΣΠΙΤΑΚΙ, ΣΠΙΤΑΛΙ, ΣΠΙΤΙ, ΣΠΙΤΙΑ, ΣΠΙΤΙΚΑ, ΚΑΤΙ, ΣΠΛΙΤ, ΣΤΑ, ΚΑΤΣ, ΣΤΑΛΙΚΙ, ΚΙΑΛΙ, ΚΙΛΑ, ΚΙΤ, ΚΙΤΑΠΙ, ΚΙΤΣ, ΚΛΑΙΣ, ΚΛΑΙΣΤ, ΚΛΙΠ, ΚΛΙΤΑ, ΛΙΠΑΤΙ, ΛΙΠΙ, ΛΙΣΑΚ, ΛΙΣΤ, ΛΙΣΤΑ, ΛΙΤΑ, ΣΤΙΛ, ΠΑΛΙ, ΠΑΛΙΣ, ΠΑΣ, ΠΑΣΙ, ΠΑΤΙ, ΠΑΤΙΚΙ, ΠΑΤΣΙ, ΠΙΑ, ΠΙΚ, ΠΙΚΑ, ΠΙΚΑΣ, ΠΙΣΑ, ΠΙΣΤΑ, ΠΙΣΤΑ, ΠΙΤ, ΠΙΤΑ, ΠΙΤΑΣ, ΠΙΤΣΑ, ΠΙΤΣΙΚΑ, ΠΙΤΣΙΛΑ, ΠΙΤΣΙΛΑ, ΠΛΑΙ, ΠΛΑΚΙ, ΤΑ, ΤΑΚ, ΤΑΛΚ, ΤΑΠΙ, ΤΑΣΙ, ΤΙ, ΤΙΚ, ΤΙΚΑΣ, ΤΙΛΙΑ, ΤΙΛΙΑ, ΤΙΣ, ΤΣ, ΤΣΑ, ΤΣΑΙ, ΤΣΑΚ, ΤΣΑΛΙ, ΤΣΑΠΙ, ΤΣΙΚ, ΤΣΙΚΛΑ, ΤΣΙΛΙΑ, ΤΣΙΛΙΚΑ, ΤΣΙΠ, ΤΣΙΠΑ, ΣΑ

 

Έχω κάνει όλες τις λέξεις capitalize κι έχω αφαιρέσει τους τόνους. Προφανώς θέλει δουλειά από εκεί και πέρα, ίσως μια αντιστοίχιση κάθε λέξης με τονισμό και χωρίς.

[defacer]

το σκέφτηκα σαν καλή ιδέα να πειραματιστώ λίγο (και με τους αλγορίθμους αναζήτησης). C, είναι η γλώσσα που θα το υλοποιήσω. έχω ήδη σκεφτεί πάνω κάτω τον αλγόριθμο (μάλλον δυαδικό δένδρο).

 

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

 

Ο αλγόριθμος θα έρθει όταν φτάσεις στη φάση της υλοποίησης, όχι νωρίτερα. Μέχρι τότε αρκεί να σκέφτεσαι στο επίπεδο "θα βρούμε αν υπάρχει όμοιο" ξέρωντας ότι το πώς ακριβώς θα το βρούμε μπορεί να απαντηθεί αργότερα. Διαφορετικά ρισκάρεις να κολλήσεις στις λεπτομέρειες που έτυχε να σκεφτείς, να αποκτήσεις το XY problem και να μη μπορείς να κάνεις πρόοδο.

[developergrxp]

https://www.dropbox.com/s/puhnkgvx3fcf22g/create_dic.zip?dl=0

 

Εκει εφτιαξα ενα προγραμματακι σε 5 λεπτα που κανει υπολογισμους και παραγει τις λεξεις.

Σε i7 Cpu φτιαχνει τα 2.5 δισεκατομυρια συνδιασμους σε 11 δευτερολεπτα.

Το Θεμα που εθεσε ο φιλος ειναι πολυπλοκο ζητησε τον πιο fast αλγοριθμο και θεωρω οτι πιο fast απο αυτον τον τροπο δεν γινετε.

Το προγραμμα ειναι σε pascal size of file 135.168 

to sha1 απο το create_dic.exe  ειναι
 7da016845e87372a8034c8871939b7fcd11b03e2 
 

το sha1 απο create_dic.zip
2def86ab763f39eab044ddd050051870eb80ccc3 


Αν βγει κατι πιο γρηγορο απο αυτο σπαω τα πισια μου

 

και εικονα απο το προγραμματακι
https://www.dropbox.com/s/cuaw10jf9hfewg8/createdir_thumb.png?dl=0

[defacer]

Το Θεμα που εθεσε ο φιλος ειναι πολυπλοκο ζητησε τον πιο fast αλγοριθμο και θεωρω οτι πιο fast απο αυτον τον τροπο δεν γινετε.

 

Αναμένουμε περισσότερες πληροφορίες σχετικά με το ποιός είναι "αυτός ο τρόπος" (υπάρχει κάτι περίεργο μέσα; στην ουσία ένας απλός μετρητής είναι σε αυθαίρετα επιλεγμένη αριθμητική βάση) και γιατί δε γίνεται γρηγορότερα. Not that it matters στην ουσία, είναι αρκετά γρήγορο έτσι κι αλλιώς.

[SIMkartaUK]

Στο βιβλίο Sams Algorithms in 24 hours που (δυστυχώς) ακόμα διαβάζω έχει ένα ωραίο παράδειγμα anagram στη σελίδα 221 για το recursion.. ρίξε μιά ματιά για εμπνευση.. 

[pmav99]

Σε ποια έκδοση;