Distancia de bigramas

Universidad de Costa Rica. Escuela de Ciencias de la Computación e Informática.
CI-0113 Programación II. I-2025. Examen 01 [14-May-2025]

Instrucciones. Dispone de 3 horas para realizar el examen. Es obligatorio apagar el celular y cualquier otro dispositivo de comunicación. Utilice únicamente los conceptos y técnicas vistos en clases para resolver el problema. No está permitido el uso de colecciones de la biblioteca estándar ni de terceros. Puede utilizar std::string. Se evaluarán las buenas prácticas de programación, las convenciones de estilo y la indentación. Puede consultar sus notas en máximo una hoja manuscrita original previamente elaborada, la cual debe entregar junto con este enunciado y su cuaderno de examen al finalizar la prueba. Asegúrese de firmar la hoja de asistencia al salir.

En varias áreas de la computación, como la recuperación de información (ej.: buscadores de documentos web), es indispensable comparar textos. Saber si dos textos son exactamente iguales no es tan útil como determinar qué tan similares son. Hay varios algoritmos para determinar qué tan similares o distintos son dos textos. Uno de ellos es la distancia basada en bigramas.

Un bigrama es un par de caracteres consecutivos pertenecientes a un término (o palabra). Por ejemplo, AR es un bigrama dentro de ARROZ, PASEAR, CARTA, y ARMAR, pero no es un bigrama presente en RATA, CAER ni CAMPO.

Para un término o palabra se pueden obtener todos sus bigramas simplemente agrupando sus caracteres consecutivos en pares. Por ejemplo, separar la palabra PAPAYA en bigramas genera los cinco bigramas PA-AP-PA-AY-YA. Para el cálculo de la distancia de bigramas es útil descartar los bigramas reiterados. Conviene construir el conjunto de bigramas de un término, ya que matemáticamente los conjuntos no permiten la repetición de elementos. Si t es el término t = "PAPAYA", su conjunto de bigramas sería T = {PA, AP, AY, YA}. La cantidad de bigramas en el conjunto, conocido cardinalidad |T| es 4 en nuestro ejemplo, uno menos que la lista de 5 bigramas original, dado que el bigrama PA estaba repetido.

Supóngase que queremos comparar dos términos t₁ y t₂ para saber qué tan distintos son. La distancia de bigramas entre ellos sería un número real entre [0, 1], donde un valor cercano a 1 indicaría que los textos tienen poco en común (mayor distancia), y un valor cercano a 0, indicaría que los textos tienen mucho en común (menor distancia), y se calcula con la relación:

\[d(t_1, t_2) = 1 - \frac{2 \cdot |T_1 \cap T_2|}{|T_1| + |T_2|}\]

donde t₁ y t₂ son los términos a comparar, T₁ y T₂ son sus respectivos conjuntos de bigramas, |T₁| y |T₂| son las cardinalidades de esos conjuntos, y |T₁ ∩ T₂| es la cardinalidad de la intersección entre ambos conjuntos, es decir, la cantidad de bigramas en común entre ambos términos.

Por ejemplo, si la primera palabra a comparar es t₁ = PAPAYA, su conjunto de bigramas sería T₁ = {PA, AP, AY, YA} y su cardinalidad sería |T₁| = 4. Si la segunda palabra a comparar es t₂ = PAYASO, su conjunto de bigramas sería T₂ = {PA, AY, YA, AS, SO} y su cardinalidad sería |T₂| = 5. La intersección de ambos conjuntos es T₁ ∩ T₂ = {PA, AY, YA} y su cardinalidad es |T₁ ∩ T₂| = 3. Por lo tanto, la distancia de bigramas entre ambos términos sería:

\[d(t_1, t_2) = 1 - \frac{2 \cdot 3}{4 + 5} = 1 - \frac{6}{9} = 1 - \frac{2}{3} = \frac{1}{3} \approx 0.333\]

La siguiente tabla muestra la distancia de bigramas entre t₁ = PAPAYA y otros términos, entre los cuales, el más similar es PAYASO y el más distinto es RATA:

t₂ T₂ |T₂| T₁ ∩ T₂ |T₁ ∩ T₂| d(t₁, t₂)

t₂	T₂	\|T₂\|	T₁ ∩ T₂	\|T₁ ∩ T₂\|	d(t₁, t₂)
`PAYASO`	`{PA, AY, YA, AS, SO}`	`5`	`{PA, AY, YA}`	`3`	`0.333333`
`KAYAK`	`{KA, AY, YA, AK}`	`4`	`{AY, YA}`	`2`	`0.5`
`AY`	`{AY}`	`1`	`{AY}`	`1`	`0.666667`
`RATA`	`{RA, AT, TA}`	`2`	`{ }`	`0`	`1`

PAYASO

{PA, AY, YA, AS, SO}

5

{PA, AY, YA}

3

0.333333

KAYAK

{KA, AY, YA, AK}

4

{AY, YA}

2

0.5

AY

{AY}

1

{AY}

1

0.666667

RATA

{RA, AT, TA}

2

{ }

0

1

Elabore un programa que calcule la distancia de bigramas entre el término que recibe en la primera línea de la entrada estándar (llamado término de referencia), contra los términos que vienen en las siguientes líneas (términos a comparar). Compare también el término de referencia contra sí mismo, para comprobar que su distancia es 0.

Ejemplo de entrada	Ejemplo de salida
PAPAYA PAYASO KAYAK RATA AY	PAPAYA PA-AP-AY-YA 0 PAYASO PA-AY-YA-AS-SO 0.333333 KAYAK KA-AY-YA-AK 0.5 RATA RA-AT-TA 1 AY AY 0.6

Ejemplo de entrada

Ejemplo de salida

PAPAYA

PAYASO
KAYAK
RATA
AY

PAPAYA PA-AP-AY-YA 0
PAYASO PA-AY-YA-AS-SO 0.333333
KAYAK KA-AY-YA-AK 0.5
RATA RA-AT-TA 1
AY AY 0.6

Se quiere que el programa muestre en la salida estándar cada término a comparar, su conjunto de bigramas, y la distancia de bigrama respecto al término de referencia.

Evaluación

En cada uno de los rubros siguientes se evalúan las buenas prácticas de programación que influyen en la calidad, eficiencia, y reutilización del código. Nota: no es necesario que documente con Doxygen.

[10%] Subrutina principal. Compara el término de referencia contra todas los demás en las líneas de la entrada.
[20%] Representa un término y su conjunto de bigramas. Libera memoria.
[15%] Lee términos desde la entrada estándar. Imprime su texto y conjunto de bigramas en la salida estándar.
[20%] Separa los bigramas y los agrega al conjunto sin permitir repetidos.
[20%] Calcula la distancia de bigramas entre dos términos. Calcula la cardinalidad de la intersección de los conjuntos de bigramas.
[15%] Representa bigramas. Permite compararlos. Imprime bigramas en la salida estándar.