El algoritmo de Ratcliff/Obershelp en SuperBASIC

El algoritmo Ratcliff/Obershelp consiste en una estrategia para calcular la similitud entre dos cadenas de caracteres. Para este cálculo se emplean el número de caracteres coincidentes dividido por el número total de caracteres en las dos cadenas. La búsqueda de las coincidencias se basa en ir hallando la mayor sub-secuencia de caracteres en común entre las dos cadenas de forma recursiva.

El algoritmo está diseñado para comparar dos cadenas y devolver un porcentaje que represente la similitud o lo cerca que están la una de la otra. Un resultado de 67 significa que las dos cadenas tienen un porcentaje de igualdad del 67%.

Podríamos usarlo para comparar una palabra mal escrita con una serie de posibles palabras correctas en el corrector ortográfico de un procesador de textos. La palabra con el mayor porcentaje de igualdad se tomaría como la ortografía correcta de la palabra. También podríamos emplear esta rutina en algún juego conversacional en el que quisiéramos ayudar al usuario en caso de que comenta errores ortográficos o tipográficos.

El programa es un buen ejemplo de cómo utilizar la recursividad en SuperBASIC. El algoritmo toma las dos palabras y extrae la mayor subcadena común coincidente entre ellas (llamemos a esta subcadena MSC). Para cada cadena, se toma la parte de la palabra a la izquierda y a la derecha de la MSC y con esta sub-cadenas se vuelve a repetir el proceso comparando unas y otras. El proceso finaliza cuando la cadena completa es analizada.

Como ejemplo, echemos un vistazo a las dos palabras “pennsylvania” y “pencilvaneya”. La MSC es “lvan”. El programa toma entonces las subcadenas s más a la izquierda de ambas palabras (“Pennsy” y “penci”) y las procesa siguiendo la misma estrategia. La MSC es ahora “pen”. Dado que no hay nada a la izquierda de la MSC (“pen” en este caso), el programa intenta entonces el lado derecho, “NSY” y “ci”. Con estas dos cadenas, no hay MSC. El programa entonces sube hacia arriba en el árbol y trata las otras subcadenas de la derecha, “ia” y “eya”. Esto continúa hasta que todas las subcadenas se analizan.

La implementación que presentamos en SuperBASIC consiste en una función que devuelve un valor con el “parecido” de las dos cadenas que vamos a analizar.

Podemos invocar a la función de la siguiente manera:

   x = percent_alike(a$,b$) 

Siendo a$ y b$ las variables de cadena que queremos comparar.

La función puede tomar también literales como argumentos, por ejemplo:

   x = percent_alike("sofware","softwear")

Hay que tener en cuenta que el programa distingue mayúsculas y minúsculas, con lo cual hay que convertir las dos cadenas a mayúsculas o a minúsculas antes de realizar la comparación.

A continuación mostramos el código fuente en SuperBASIC de este algoritmo.

100 REMark Test ---
110 CLS
120 x = percent_alike("sofware","softwear")
130 PRINT "Percent alike: sofware - software", x
140 STOP
150 :
160 :
170 DEFine FuNction percent_alike(a$,b$)
180   LOCal total
190   total = num_alike(a$,b$)
200   RETurn INT( total/(LEN(a$)+LEN(b$))*100)
210 END DEFine percent_alike
220 :
230 :
240 DEFine FuNction num_alike (a$, b$)
250   LOCal total, temp$, a1, a2, b1, b2, large$
260   total = 0
270   IF a$=b$ THEN RETurn LEN(a$)*2
280   IF LEN(a$)=1 AND LEN(b$)=1 THEN RETurn 0
290   REMark  ** make a$ the shortest string
300   IF LEN(a$) > LEN(b$) THEN
310     temp$ = a$
320     a$ = b$
330     b$ = temp$
340   END IF
350   REMark ** if a$ = one char and b$ > one char
360   IF LEN(a$)=1 THEN RETurn (a$ INSTR b$)
370   large$ = find_gt_com$ (a$, b$)
380   IF large$ = "" THEN RETurn 0
390   length = LEN(large$)
400   total = length*2
410   a1 = large$ INSTR a$
420   a2 = a1 + length
430   b1 = large$ INSTR b$
440   b2 = b1 + length
450   IF (a1>1) OR (b1>1) THEN
460     total = total+num_alike (a$(1 TO (a1-1)), b$(1 TO (b1-1)))
470   END IF
480   IF (a2LEN(a$)+1) OR (b2LEN(b$)+1) THEN
490     total = total+num_alike (a$(a2 TO), b$(b2 TO))
500   END IF
510   RETurn total
520 END DEFine num_alike
530 :
540 :
550 DEFine FuNction find_gt_com$ (a$, b$)
560   LOCal temp$, i, j, temp, large$
570   IF LEN(a$) > LEN(b$) THEN
580     temp$ = a$
590     a$ = b$
600     b$ = temp$
610   END IF
620   LET large$=""
630   FOR i = 1 TO LEN(a$)
640     FOR j = i TO LEN(a$)
650       temp = a$(i TO j) INSTR b$
660       IF (temp0) AND (LEN(a$(i TO j))>LEN(large$)) THEN
670         large$=a$(i TO j)
680       END IF
690     END FOR j
700   END FOR i
710   RETurn large$
720 END DEFine find_gt_com

—–
Fuente:
Ratcliff/Obershelp Pattern Matching (por Tim Swenson)
QL Hacker’s Journal
—–

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s