levenshtein

Περιγραφή

Η συνάρτηση αυτή επιστρέφει την απόσταση Levenshtein μεταξύ δύο strings ορισμάτων ή την τιμή -1, εάν κάποιο από τα string ορίσματα είναι μεγαλύτερο από το όριο των 255 χαρακτήρων (οι 255 χαρακτήρες είναι περισσότερο από αρκετοί για ονόματα ή συγκρίσεις σε λεξικά, και επιπλέον κανείς δεν πρόκειται να κάνει γεννετική ανάλυση με την PHP).

Η απόσταση Levenshtein ορίζεται ως ο ελάχιστος αριθμός χαράκτηρων που πρέπει να αντικατασταθούν, να εισαχθούν ή να διαγραφούν για να μετατραπεί το string str1 στο str2 . Η πολυπλοκότητα του αλγορίθμου είναι O(m*n), όπου οι παράμετροι n και m είναι τα μήκη του str1 και του str2 αντίστοιχα. Η πολυπλοκότητα αυτή είναι αρκετά καλή συγκρινόμενη με αυτήν της συνάρτησης similar_text(), η οποία είναι O(max(n,m)**3), παραμένει, όμως, μεγάλη.

Στην πιο απλή της μορφή η συνάρτηση θα πάρει σαν παραμέτρους μόνο τα δύο strings και θα υπολογίσει μονάχα το πλήθος των εισαγωγών, διαγραφών και αντικαταστάσεων που χρειάζονται για τη μετατροπή του str1 σε str2 .

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

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

Η παρεχόμενη από το χρήστη συνάρτηση θα καλείται με τα ακόλουθα ορίσματα:

• λειτουργία που θα εκτελεστεί: 'I', 'R' ή 'D'
• πραγματικός χαρακτήρας στο string 1
• πραγματικός χαρακτήρας στο string 2
• θέση στο string 1
• θέση στο string 2
• υπολοιπόμενοι χαρακτήρες στο string 1
• υπολοιπόμενη χαρακτήρες στο string 2

Η παρεχόμενη από το χρήστη συνάρτηση πρέπει να επιστρέφει ένα θετικό integer που περιγράφει το κόστος της ενέργειας, αλλά μπορεί και να επιλέγει τη χρήση μερικών μόνο από τα παρεχόμενα ορίσματα.

Η παρεχόμενη από το χρήστη συνάρτηση προσφέρει τη δυνατότητα να ληφθεί υπ' όψιν η σχέση και/ή η διαφορά μεταξύ κάποιων συμβόλων (χαρακτήρων) ή ακόμα και το γενικό πλαίσιο στο οποίο εμφανίζονται τα σύμβολα αυτά, προκειμένου να υπολογιστεί το κόστος εισαγωγής, αντικατάστασης και διαγραφής, αλλά όλα αυτά εις βάρος των βελτιστοποιήσεων που έγιναν στη χρήση των καταχωρητών της cpu και των αστοχιών της cache κατά τις προηγούμενες παραλλαγές.

Ανατρέξτε επίσης στις: soundex(), similar_text(), και metaphone().