Cuando estamos programando motores que pretenden emular a un ser humano, debemos comparar la similitud de muchos datos. El problema de las comparativas son que un ser humano tiene sentido común, un software NO.
Existen muchos casos dónde es necesario comparar cadenas de texto más allá de la comparativa usual:
Código :
if(cadena_1 == cadena_2) algo : otro;
Y más bien necesitan algo como:
Código :
if(cadena_1 {se_parece_a} cadena_2) algo:otro;
Para esto usaremos la Distancia de Levenshtein. Que en realidad suena algo MUY complejo pero no lo es. En este tip intentaré explicar la manera de analizar algo con este algoritmo, no como funciona en sí mismo, ya que hasta PHP trae una función para solucionarlo.
Encontrar palabras similares aún con errores
Imaginen un caso simple, debemos detectar en nuestra base de datos quienes han tipeado mal el país. Ya que queremos implementar un sistema experto que analice de cada país viene cada uno como una subrutina. El problema, es que los datos están en String no Int.
Entonces para realizar el sistema, imaginen tenemos esto:
Código :
Freddie Colomia (En vez de Colombia) Hernán Aregntina (En vez de Argentina)
Y otra tabla de países donde diremos:
Código :
Argentina ID = 1 Colombia ID = 2
El resultado final esperado será:
Código :
Freddie = 2 Hernan = 1
Traer los datos de países para comparación con el texto a detectar
No tiene sentido analizar toda la base de datos con la distancia de Levenshtein, ya que solo algunos pocos esperamos tengan problema (En nuestro ejemplo, Freddie y Hernán).
Por lo cual primero modelaremos un pequeño GPS (que ya vimos en otro tip) para procesar correctamente sin usar recursos extra:
Modelo GPS para Análisis:
- Buscar con Inner Join en la tabla Usuarios y tabla Países
- Todos estos resultados editarlos dándoles su value de país
- Buscar todos los resultados que hayan quedado sin valor (int !=0)
- Eliminar espacios en blanco de la cadena y pasar a minúsculas
- Seleccionar en la base de datos los más similares a la cadena a analizar
- Eliminar espacios en blanco de los resultados y pasar a minúsculas
- Aplicar distancia de Levenshtein
- Aplicar el valor más cercano al país
Algoritmo Levenshtein
En la propia Wikipedia podrán encontrar el algoritmo con muchas aplicaciones, sin embargo dejo aquí las dos más usadas para Clab (PHP y AS3).
Código :
public class StringUtils { public static function levenshtein(s1:String, s2:String):int { if (s1.length == 0 || s2.length == 0) return 0; var m:uint = s1.length + 1; var n:uint = s2.length + 1; var i:uint, j:uint, cost:uint; var d:Vector.<Vector.<int>> = new Vector.<Vector.<int>>(); for (i = 0; i < m; i++) { d[i] = new Vector.<int>(); for (j = 0; j < n; j++) d[i][j] = 0; } for (i = 0; i < m; d[i][0] = i++) ; for (j = 0; j < n; d[0][j] = j++) ; for (i = 1; i < m; i++) { for (j = 1; j < n; j++) { cost = (s1.charAt(i - 1) == s2.charAt(j - 1)) ? 0 : 1; d[i][j] = Math.min(Math.min(d[i - 1][j] + 1, d[i][j - 1] + 1), d[i - 1][j - 1] + cost); } } return d[m-1][n-1]; } }
Código :
<?php $lev = levenshtein($input, $word); ?>
Cuando usar la Distancia de Levenshtein
Conocer la existencia de este algoritmo de distancia entre Strings es muy útil para correctores ortográficos, buscar similitudes de búsqueda, encontrar errores de tipeo, etc. Y por sobre todo, es genial para evitar cagar comparativas en sistemas expertos que requieren de un aprendizaje estandarizado.
¿Sabes SQL? ¿No-SQL? Aprende MySQL, PostgreSQL, MongoDB, Redis y más con el Curso Profesional de Bases de Datos que empieza el martes, en vivo.
Por gersonm el 06 de Octubre de 2010
Por Hernán el 06 de Octubre de 2010
gersonm-blog :
Pues a ser sincero no he armado nunca pruebas con cadenas fuera de índices, generalmente la uso combinada en partes más grandes. Ahora la estoy usando para comparar pequeñas sub-partes para un sistema de predicción por ejemplo. La he usado para cruzar datos, datewarehousing, etc.
Nunca probé hacerlo con cadenas largas, pero me veo tentado, mañana montaré una prueba en un servidor real (No mi PC), y te cuento que tal me fue. Interesante pregunta realmente.
Por cierto, SOLO la he usado desde PHP nunca desde AS.
Saludos, Hernán . -
Por daz_angie el 07 de Octubre de 2010
Sería cuestión de ver realmente la rapidez con la que hace el proceso.
Y si no es tan bueno en rendimiento, buscar una alternativa u optimizar el mismo algoritmo
Eso es lo lindo de la AI, poder cambiar los algoritmos para que a ti te funcionen mejor...
Por tomasdev el 09 de Octubre de 2010
Por esutoraiki el 11 de Octubre de 2010
Argentina ID = 5
Por Maikel el 27 de Octubre de 2010
gersonm-blog :
Hice pruebas con la base de datos de cristalab y el rendimiento no es muy bueno en verdad. Por lo que usar levenshtein solo sin métodos de discriminación alternos no seria una opción viable.
Las cadenas no deberían ser largas, mientras mas largas las cadenas peor el rendimiento.
saludos
Por Maikel el 27 de Octubre de 2010
He estado haciendo pruebas trayéndome todos los datos de la tabla a php para hacer los cálculos con las mismas funciones en php y el rendimiento fue increíblemente mejor.
De todas maneras, estas pruebas que estoy haciendo no son por mera curiosidad sino porque tengo que usarlo realmente. Cuando lo implemente daré mis resultados y sugerencias.
Por Iliana Burguan el 29 de Abril de 2011
Por Mc Mclain el 18 de Febrero de 2013
Por el 31 de Enero de 2018
classroom rental space
training rrom rental in singapore
training rooms in singapore
seminar room rental in singapore
indoor team building activities
corporate team building games singapore
team bonding in singapore
team building activities singapore
team building games singapore
10 soft skills you need
administrative office procedures
administrative support courses
adult learning mental skills
adult learning physical skills
anger management courses in singapore
appreciative inquiry courses
archiving and records management
assertiveness and self confidence
attention management courses
basic bookkeeping courses
being a likeable boss
body language basics courses
budgets and financial reports
business acumen courses
business ethics courses
business etiquette courses in singapore
business succession planning courses
business writing courses in singapore
call center training courses
change management courses in singapore
coaching and mentoring courses
coaching sales people courses
collaborative business writing
communication strategies courses
conducting annual employee reviews
conflict resolution courses
contact center training courses
contract management courses in singapore
creating a great webinar
creative problem solving courses
crisis management courses
critical thinking courses in singapore
customer service courses in singapore
customer support courses
cyber security courses in singapore
delivering constructive criticism
developing a lunch and learn
developing corporate behavior
developing creativity courses
developing new managers
digital citizenship courses
emotional intelligence courses
employee motivation courses
employee on boarding courses
employee recognition courses
employee recruitment courses
employee termination processes
entrepreneurship courses in singapore
event planning courses in singapore
executive and personal assistants
facilitation skills courses
generation gaps courses
goal setting and getting things done
handling a difficult customer
health and wellness at work courses
high performance teams inside the company
high performance teams remote work force
hiring strategies courses
human resource management courses in singapore
improving mindfulness
improving self awareness
increasing your happiness
internet marketing fundamentals courses
interpersonal skills courses
job search skills courses
knowledge management courses in singapore
leadership and influence courses
lean process and six sigma
life coaching essentials courses
manager management courses
managing personal finances courses
managing work place anxiety
marketing basics courses
measuring results from training
media and public relations courses
meeting management courses
middle manager courses
millennial on boarding courses
m learning essentials
motivating your sales team
multi level marketing courses
negotiation skills courses
networking outside the company
networking within the company
office politics for managers
organizational skills courses
overcoming sales objections
performance management courses
personal branding courses in singapore
personal productivity courses
presentation skills courses in singapore
project management courses in singapore
proposal writing courses
prospecting and lead generation
public speaking courses in singapore
risk assessment and management courses
safety in the work place courses
sales fundamentals courses
sales training courses in singapore
servant leadership courses
it courses in singapore
microsoft training singapore
corporate training in singapore
corporate sgx
social intelligence courses
social learning courses
social media in the work place
social media marketing courses in singapore
soft skills courses in singapore
stress management courses in singapore
supervising others
supply chain management courses
taking initiative courses
talent management courses
team building for managers
team building through chemistry
teamwork and team building
telephone etiquette courses
telework and telecommuting
time management courses in singapore
trade show staff training
train the trainer courses
virtual team building and management
women in leadership courses
work life balance courses in singapore
work place diversity courses
work place harassment courses
work place violence courses
sancy suraj
sancy suraj
sancy suraj
sancy suraj
sancy suraj
sancy suraj
sancy suraj
sancy suraj
[url=https://books.google.com.sg/books?id=1QykBQAAQBAJ&pg=PT362&lpg=PT362&dq=%22sancy+suraj+singh%22&source=bl&ots=E86QDyrLG2&sig=H-6a_YH-kTWaZWTfPSr1xfm4BOs&hl=en&sa=X&ved=0ahUKEwi3_56hhubVAhWJLo8KHcxTBxQ4ChDoAQgjMAA#v=onepage&q =% 22sancy% 20suraj% 20singh% 22 & f = false]sancy suraj[/url]
sancy suraj
longest colour sequence memorised
sancy suraj
longest colour sequence memorised
memory training course
memory training course
memory training course
memory training course
memory training course
memory training course
memory training course
memory training course
memory training course
memory training course
memory training course
memory training course
memory training course
memory training course
memory training course
memory training course
memory training course
memory training course
lunch talks
lunch talks
memory training course
memory training course
cabin crew
online memory course
memory training course
memory training course
memory training course
memory training course
memory training course
speed reading
tuition
tuition
tuition
tuition
tuition
tuition
tuition
tuition
tuition
tuition
geography tuition for secondary school students in singapore
geography tuition for secondary school students singapore
geography tuition for secondary school students singapore
geography tuition for secondary school students singapore
geography tuition for secondary school students singapore
secondary geography tuition in singapore
history tuition for secondary school students in singapore
social studies tuition for secondary school students in singapore
psle english tuition in singapore
psle science tuition in singapore
secondary 1 chemistry tuition in singapore
secondary 1 physics tuition in singapore
school holiday workshops courses for students in singapore
school holidays activitie in singapore
school holidays activitie in singapore
[url=http://umonictuitionadvantage.com/2017-november-school-holidays-activities-programmes-workshop-courses-camps-for- students-kids-in-singapore/]school holidays activitie in singapore[/url]
school holidays activitie in singapore
study skills
study skills
study skills workshops course in singapore
study skills workshops course in singapore
speed reading
speed reading
tuition
tuition
tuition
tuition
tuition
tuition
tuition
tuition
tuition
tuition
tuition
tuition
tuition
tuition
tuition
tuition[
tuition[
tuition[
tuition[
tuition[
tuition[
tuition[
tuition[
student courses
corporate training
corporate training
corporate training
corporate training
corporate training
corporate training
corporate training
corporate training
corporate training
corporate training
corporate training
corporate training
corporate training
corporate training
corporate training
corporate training
corporate training
corporate training
corporate training
corporate training
corporate training
corporate training
lunch talk
lunch talk
lunch talk
lunch talk
lunch talk
lunch talk
lunch talk
lunch talk
lunch talk
lunch talk
lunch talk
lunch talk
corporate lunch talk
corporate lunch talk
corporate lunch talk
corporate lunch talk
corporate lunch talk
corporate lunch talk
corporate lunch talk
corporate lunch talk
corporate lunch talk
corporate lunch talk
corporate lunch talk
corporate lunch talk
corporate lunch talk
corporate lunch talk
team building
team building ideas
team building activities
unique team building
team building
corporate training in singapore
corporate training courses
corporate training courses
corporate training courses
corporate training courses
corporate health talk
corporate health talk
corporate health talk
lunch and learn talk
workplace lunch and learn
corporate training companies in singapore
training companies in singapore
emcee
emcee
health talks
soft skills training course
corporate training providers
professional development courses
training and development courses
short courses in singapore
corporate training courses in singapore
corporate training courses
corporate training in singapore
school holiday workshops courses for students in singapore
business students memory course in singapore
business students memory improvement workshop in singapore
memory improvement course for business students
memory improvement course for business students
business students memory improvement course
business students memory course in singapore
corporate health talks singapore
corporate health talks in singapore
corporate health talk singapore
corporate health talk in singapore
corporate health talks singapore
corporate health talks singapore
finance students memory training course in singapore
finance students memory training course in singapore
finance students memory training course in singapore
memory training courses for finance students in singapore
memory training courses for finance students in singapore
memory improvement courses for finance students in singapore
pinnacle minds
memory course
study skills
speed reading
memory training
school holiday
lunch and learn
march school holidays workshops
march school holidays workshops
march school holidays workshops
march school holidays workshops
march school holidays workshops
june school holidays workshops
june school holidays workshops
june school holidays workshops
june school holidays workshops
september 2018 school holidays workshops
september 2018 school holidays workshops
september 2018 school holidays workshops
september 2018 school holidays workshops
november 2018 school holidays workshops
november 2018 school holidays workshops
november 2018 school holidays workshops
november 2018 school holidays workshops
december 2018 school holidays workshops
december 2018 school holidays workshops
december 2018 school holidays workshops
december 2018 school holidays workshops
top 10 soft skills you need training course
administrative office procedures training course
administrative support training course
anger management training course
appreciative inquiry training course
archiving and records management training course
archiving and records management training course
self confidence and assertiveness training course
improving your attention management training course
bacis bookkeeping training course
being a likeable boss training course
body language training course
budgets and-financial reports training course
business acumen training course
business ethics training course
business etiquette training course
business succession planning training course
business writing training course
call centre training course
change management training course
civility in the workplace training course
coaching and mentoring training course
coaching salespeople training course
collaborative business writing training course
communication strategies training course
conducting annual employee reviews training course
conflict resolution training course
contact centre training course
contract management training course
creating a great webinar training course
creative problem solving training course
crisis management training course
critical thinking training course
customer service training course
customer support training course
cyber security training course
delivering constructive criticism training course
developing lunch and learn training course
developing corporate behavior training course
developing creativity training course
developing new managers training course
digital citizenship training course
emotional intelligence training course
employee motivation training course
employee onboarding training course
employee recognition training course
employee recruitment training course
employee termination processes training course
entrepreneurship training course
event planning training course
executive and personal assistants training course
facilitation skills training course
generation gaps training course
goal setting and getting things done training course
handling a difficult customer training course
health and wellness at work training course
high performance teams inside the company training course
high performance teams remote workforce training course
hiring strategies training course
human resource management training course
improving mindfulness training course
improving self awareness training course
internet marketing fundamentals training course
interpersonal skills training course
job search skills training course
knowledge management training course
leadership and influence training course
lean process and six sigma training course
life coaching essentials training course
manager management training course
managing personal finances training course
managing workplace anxiety training course
marketing basics training course
measuring results from training course
media and public relations training course
meeting management training course
middle manager training course
millennial onboarding training course
mlearning essentials training course
motivating your sales team training course
negotiation skills training course
networking outside the company training course
networking within the company training course
office politics for managers training course
organizational skills training course
overcoming sales objections training course
performance management training course
personal branding training course
personal productivity training course
presentation skills training course
project management training course
proposal writing training course
prospecting and lead generation training course
public speaking training course
risk assessment and management training course
safety in the workplace training course
sales fundamentals training course
servant leadership training course
social intelligence training course
social learning training course
social media in the workplace training course
social media marketing training course
stress management training course
supervising others training course
supply chain management training course
taking initiative training course
talent management training course
team building for managers training course
team building through chemistry training course
teamwork and team building training course
telephone etiquette training course
telework and telecommuting training course
time management training course
top 10 sales secrets training course
trade show staff training course
train the trainer training course
virtual team building and management training course
women in leadership training course
work life balance training course
workplace diversity training course
workplace harassment training course
workplace violence training course
half day memory improvement courses workshops
speed reading courses workshops in singapore
10 soft skills you need corporate training course in singapore
administrative office procedures corporate training course in singapore
administrative support corporate training course in singapore
anger management corporate training course in singapore
appreciative inquiry corporate training course in singapore
archiving and records management corporate training course in singapore
self confidence assertiveness corporate training course in singapore
improving your attention management corporate training course in singapore
basic bookkeeping corporate training course in singapore
being a likeable boss corporate training course in singapore
body language basics corporate training course in singapore
budgets and financial reports corporate training course in singapore
business acumen corporate training course in singapore
business ethics corporate training course in singapore
business etiquette corporate training course in singapore
business succession planning corporate training course in singapore
business writing corporate training course in singapore
call center corporate training course in singapore
change management corporate training course in singapore
civility in the workplace corporate training course in singapore
coaching and mentoring corporate training course in singapore
coaching salespeople corporate training course in singapore
collaborative business writing corporate training course in singapore
communication strategies corporate training course in singapore
conducting annual employee reviews corporate training course in singapore
conflict resolution corporate training course in singapore
contact center corporate training course in singapore
contract management corporate training course in singapore
creating a great webinar corporate training course in singapore
creative problem solving corporate training course in singapore
crisis-management corporate training course in singapore
critical thinking corporate training course in singapore
customer service corporate training course in singapore
customer support corporate training course in singapore
cyber security corporate training course in singapore
delivering constructive criticism corporate training course in singapore
developing a lunch and learn corporate training course in singapore
developing corporate behavior corporate training course in singapore
developing creativity corporate training course in singapore
developing new managers corporate training course in singapore
digital citizenship corporate training course in singapore
emotional intelligence corporate training course in singapore
employee motivation corporate training course in singapore
employee onboarding corporate training course in singapore
employee recognition corporate training course in singapore
employee recruitment corporate training course in singapore
employee termination processes corporate training course in singapore
entrepreneurship training course in singapore
event planning corporate training course in singapore
executive and personal assistants corporate training course in singapore
facilitation skills corporate training course in singapore
generation gaps corporate training course in singapore
goal setting and getting things done corporate training course in singapore
handling a difficult customer corporate training course in singapore
health and wellness at work corporate training course in singapore
high performance teams inside the company corporate training course in singapore
high performance teams remote workforce corporate training course in singapore
hiring strategies corporate training course in singapore
human resource management corporate training course in singapore
improving mindfulness corporate training course in singapore
improving self awareness corporate training course in singapore
increasing your happiness corporate training course in singapore
internet marketing fundamentals corporate training course in singapore
interpersonal skills corporate training course in singapore
job search skills corporate training course in singapore
knowledge management corporate training course in singapore
leadership and influence corporate training course in singapore
lean process and six sigma corporate training course in singapore
life coaching essentials corporate training course in singapore
manager management corporate training course in singapore
managing personal finances corporate training course in singapore
marketing basics corporate training course in singapore
measuring results from corporate training course in singapore
media and public relations corporate training course in singapore
meeting management corporate training course in singapore
middle manager corporate training course in singapore
millennial onboarding corporate training course in singapore
mlearning essentials corporate training course in singapore
motivating your sales team corporate training course in singapore
negotiation skills corporate training course in singapore
networking outside the company corporate training course in singapore
networking within the company corporate training course in singapore
office politics for managers corporate training course in singapore
organizational skills corporate training course in singapore
overcoming sales objections corporate training course in singapore
performance management corporate training course in singapore
personal branding corporate training course in singapore
personal productivity corporate training course in singapore
presentation skills corporate training course in singapore
project management corporate training course in singapore
proposal writing corporate training course in singapore
prospecting and lead generation corporate training course in singapore
public speaking corporate training course in singapore
[url