El arte de la condensacion
(no negareis que me estoy currando los titulos xD)
Estos dias pasados, hacia principios de la semana que se esta acabando, tuve que ayudar a mi estimado "vecino" y amigo alex en una importante empresa, la cual me tuvo bastante atareado durante un par de noches.
La tarea? hacer resumenes...pero unos resumenes un tanto peculiares. Por motivos de discrecionalidad no dare el detalle completo de los resumenes que tuve oportunidad de realizar, pero si hablare aqui del metodo que se siguio y de los resultados. Me gustaria comentar el tema sobre todo con gente que este en el rollo de la programacion y el desarrollo de aplicaciones, y especialmente en el tratamiento de cadenas de texto, creo que hice un trabajo bastante bueno a pesar de no contar con las aplicaciones mas apropiadas.
El objetivo consistia en la compresion de cadenas de texto con preguntas y respuestas en un formato lo mas exiguo posible.
pongamos el siguiente ejemplo, que he tomado de una pregunta al azar de los tests que estoy haciendo estos dias para la LCC (de esto hablare aqui cuando el tema este terminado)
"Si nos encontramos con un agente de espaldas con ambos brazos extendidos, ¿Que debemos hacer si deseamos seguir de frente?"
bien, imaginemonos que tenemos un compendio de digamos, 90 preguntas de las cuales esta seria una de ellas...cual seria el mejor metodo para identificar cada una de ellas de manera unica y diferenciada de las otras?
Bueno, aunque seguramente habria otros metodos mejores, el que elegimos alex y yo fue el de la codificacion utilizando columnas clave. Para ello, primero elimine los espacios entre palabras en el texto:
"Sinosencontramosconunagentedeespaldasconambosbrazosextendidos(...)"
Con esto, tenemos una larga cadena de texto. Ahora, se trata de elegir algo que permita distinguir a una linea de todas las demas y que sea una referencia fija (sino, podriamos volvernos locos a la hora de "decodificar"), para ello, habria que elegir las columnas donde mas variaciones hubiera, esto es, necesitaremos determinar en cuales de ellas se producen mas variaciones (hay menos veces las mismas letras) para poder disponer de mas claves diferentes. Por ello no son buenas las primeras letras, ya que muchas preguntas empiezan igual y por tanto, ofrecen poca variacion.
asi pues, en nuestro ejemplo de antes, dadas las siguientes lineas...
"sidejamose"
"sinosencon"
"podriaadel"
"cuandoseci"
"enqueposic"
"segunestas"
"cuandoadel"
obtenemos las siguientes lineas de "columnas clave" (esta hecho a mano, tal vez tenga algun error)
"sspcesc"
"iiouneu"
"dndaqga"
"eornuun"
"jsidend"
"aeaopeo"
"mnasosa"
"ocdestd"
"soeciae"
"enlicsl"
y aqui vemos, por ejemplo, que en el 8º grupo, no hay ninguna coincidencia, seria un buen candidato.
En el caso de nuestro estudio, resulto que la 7º columna era bastante prometedora, habiendo otras interesantes (10º, 12º, 14º, 15º, etc)
aqui hubo que resolver varias cuestiones.
* en primer lugar, y para esto solo sirvio el ensayo y error, hubo que buscar las columnas que, combinadas entre si, no tuvieran coincidencias (dos lineas diferentes que, dadas unas determinadas columnas tuvieran el mismo resultado).
* en segundo lugar hubo que elegir la longitud de la clave. esto es: cuantas columnas debian elegirse...aunque en principio parecia posible resolverlo con 2 columnas, finalmente se hizo necesario el utilizar 3 columnas.
* otra cuestion es que en la muestra, habia tanto cuestiones muy largas (con mas de 300 caracteres) como otras muy pequeñas (menos de 15). Esto hizo imposible utilizar una sola solucion para toda la muestra, ya que con la pequeña longitud de algunos de los elementos, era imposible resolver coincidencias entre otros elementos de la muestra... que empezaban con las mismas 15 letras :P
Asi que al final hubo que hacer una clave para las preguntas cortas y otra para las largas, pero no adelantemos acontecimientos... el caso es que, tras un ominoso proceso de busqueda de columnas no coincidentes, obtuvimos un resultado fiable tomando las columnas 14, 24 y 34 (la 7 hubo que descartarla por lo indicado anteriormente de las "varias lineas que empiezan todas por las mismas palabras". Asi, 24 resulto ser la primera columna que variaba en estas lineas de una manera significativa.
Asi conseguimos claves de esta guisa...
aeh
aek
aes
ain
aob
atc
cgn
chh
cnl
dpj
eab
ece
etc...
las cuales, permitian "descomprimir" cualquier pregunta del listado, por ejemplo, para nuestro ejemplo anterior...
"Sinosencontramosconunagentedeespaldasconambosbrazosextendidos(...)"
la clave seria...
"mel"
no esta mal, comprimir todo ese tochon a "mel" (mas bien, que "mel" distingue a esta lechuga entre cualquiera de las otras 90 :-P) pero aun queda la respuesta, esa parte la hizo alex, no yo, asi que no puedo hacer una descripcion pormenorizada del invento, pero si dire que la metodologia basica es la "descripcion diferencial".
por ejemplo, dadas 3 respuestas...
"si"
"no"
"no, excepto para salir"
es evidente que..
* las respuestas son demasiado cortas e iguales (muchos "si" y "no") como para usar una clave basada en columnas fijas.
* evidentemente, solo hay una respuesta correcta.
* tambien evidentemente, no tenemos el problema que con las preguntas, de que pudiera haber preguntas iguales, aqui todas son diferentes en algo
pondre el ejemplo para los 3 casos posibles.
Si la respuesta correcta fuera "si"...que lo distingue de las demas?
pues para empezar, que empieza por S y no por N, asi que ya solo con "s" tenemos la clave, si esta fuera la respuesta.
el problema es que fuera una de las otras dos la respuesta correcta, ya que es bastante mas dificil distinguir un "no" del otro "no"...
hay que buscar "que tiene un "no" que el otro no tiene" ? pues toda la coletilla, asi que cogiendo una letra cualquiera de esa coletilla, distinguiremos a ese valor.
asi que por ejemplo "x". para la 3º respuesta.
como eliminacion, la clave para la 2º seria una que no fuera valida ni para la primera, ni para la tercera, asi que podra ser la "n" o la "o".
Asi tendriamos una combinacion de pregunta respuesta tal que (por ejemplo) "mel=x"
Que para que sirve esto? usad vuestra imaginacion! :D
Pensandolo un poco...creo que me ha quedado un poco fistro este texto, pero no tengo ganas de arreglarlo mas, ea, el que quiera, que me pregunte xD
Y para concluir, como hacian no mucho tiempo ha algunos buenos amigos, recomendacion musical!
"The Voice (Eimear Quinn)"
Saludos cordiales y hasta el proximo post!
pd. este panel de texto de blogger es un poco petardo con los estilos de texto a veces...
Estos dias pasados, hacia principios de la semana que se esta acabando, tuve que ayudar a mi estimado "vecino" y amigo alex en una importante empresa, la cual me tuvo bastante atareado durante un par de noches.
La tarea? hacer resumenes...pero unos resumenes un tanto peculiares. Por motivos de discrecionalidad no dare el detalle completo de los resumenes que tuve oportunidad de realizar, pero si hablare aqui del metodo que se siguio y de los resultados. Me gustaria comentar el tema sobre todo con gente que este en el rollo de la programacion y el desarrollo de aplicaciones, y especialmente en el tratamiento de cadenas de texto, creo que hice un trabajo bastante bueno a pesar de no contar con las aplicaciones mas apropiadas.
El objetivo consistia en la compresion de cadenas de texto con preguntas y respuestas en un formato lo mas exiguo posible.
pongamos el siguiente ejemplo, que he tomado de una pregunta al azar de los tests que estoy haciendo estos dias para la LCC (de esto hablare aqui cuando el tema este terminado)
"Si nos encontramos con un agente de espaldas con ambos brazos extendidos, ¿Que debemos hacer si deseamos seguir de frente?"
bien, imaginemonos que tenemos un compendio de digamos, 90 preguntas de las cuales esta seria una de ellas...cual seria el mejor metodo para identificar cada una de ellas de manera unica y diferenciada de las otras?
Bueno, aunque seguramente habria otros metodos mejores, el que elegimos alex y yo fue el de la codificacion utilizando columnas clave. Para ello, primero elimine los espacios entre palabras en el texto:
"Sinosencontramosconunagentedeespaldasconambosbrazosextendidos(...)"
Con esto, tenemos una larga cadena de texto. Ahora, se trata de elegir algo que permita distinguir a una linea de todas las demas y que sea una referencia fija (sino, podriamos volvernos locos a la hora de "decodificar"), para ello, habria que elegir las columnas donde mas variaciones hubiera, esto es, necesitaremos determinar en cuales de ellas se producen mas variaciones (hay menos veces las mismas letras) para poder disponer de mas claves diferentes. Por ello no son buenas las primeras letras, ya que muchas preguntas empiezan igual y por tanto, ofrecen poca variacion.
asi pues, en nuestro ejemplo de antes, dadas las siguientes lineas...
"sidejamose"
"sinosencon"
"podriaadel"
"cuandoseci"
"enqueposic"
"segunestas"
"cuandoadel"
obtenemos las siguientes lineas de "columnas clave" (esta hecho a mano, tal vez tenga algun error)
"sspcesc"
"iiouneu"
"dndaqga"
"eornuun"
"jsidend"
"aeaopeo"
"mnasosa"
"ocdestd"
"soeciae"
"enlicsl"
y aqui vemos, por ejemplo, que en el 8º grupo, no hay ninguna coincidencia, seria un buen candidato.
En el caso de nuestro estudio, resulto que la 7º columna era bastante prometedora, habiendo otras interesantes (10º, 12º, 14º, 15º, etc)
aqui hubo que resolver varias cuestiones.
* en primer lugar, y para esto solo sirvio el ensayo y error, hubo que buscar las columnas que, combinadas entre si, no tuvieran coincidencias (dos lineas diferentes que, dadas unas determinadas columnas tuvieran el mismo resultado).
* en segundo lugar hubo que elegir la longitud de la clave. esto es: cuantas columnas debian elegirse...aunque en principio parecia posible resolverlo con 2 columnas, finalmente se hizo necesario el utilizar 3 columnas.
* otra cuestion es que en la muestra, habia tanto cuestiones muy largas (con mas de 300 caracteres) como otras muy pequeñas (menos de 15). Esto hizo imposible utilizar una sola solucion para toda la muestra, ya que con la pequeña longitud de algunos de los elementos, era imposible resolver coincidencias entre otros elementos de la muestra... que empezaban con las mismas 15 letras :P
Asi que al final hubo que hacer una clave para las preguntas cortas y otra para las largas, pero no adelantemos acontecimientos... el caso es que, tras un ominoso proceso de busqueda de columnas no coincidentes, obtuvimos un resultado fiable tomando las columnas 14, 24 y 34 (la 7 hubo que descartarla por lo indicado anteriormente de las "varias lineas que empiezan todas por las mismas palabras". Asi, 24 resulto ser la primera columna que variaba en estas lineas de una manera significativa.
Asi conseguimos claves de esta guisa...
aeh
aek
aes
ain
aob
atc
cgn
chh
cnl
dpj
eab
ece
etc...
las cuales, permitian "descomprimir" cualquier pregunta del listado, por ejemplo, para nuestro ejemplo anterior...
"Sinosencontramosconunagentedeespaldasconambosbrazosextendidos(...)"
la clave seria...
"mel"
no esta mal, comprimir todo ese tochon a "mel" (mas bien, que "mel" distingue a esta lechuga entre cualquiera de las otras 90 :-P) pero aun queda la respuesta, esa parte la hizo alex, no yo, asi que no puedo hacer una descripcion pormenorizada del invento, pero si dire que la metodologia basica es la "descripcion diferencial".
por ejemplo, dadas 3 respuestas...
"si"
"no"
"no, excepto para salir"
es evidente que..
* las respuestas son demasiado cortas e iguales (muchos "si" y "no") como para usar una clave basada en columnas fijas.
* evidentemente, solo hay una respuesta correcta.
* tambien evidentemente, no tenemos el problema que con las preguntas, de que pudiera haber preguntas iguales, aqui todas son diferentes en algo
pondre el ejemplo para los 3 casos posibles.
Si la respuesta correcta fuera "si"...que lo distingue de las demas?
pues para empezar, que empieza por S y no por N, asi que ya solo con "s" tenemos la clave, si esta fuera la respuesta.
el problema es que fuera una de las otras dos la respuesta correcta, ya que es bastante mas dificil distinguir un "no" del otro "no"...
hay que buscar "que tiene un "no" que el otro no tiene" ? pues toda la coletilla, asi que cogiendo una letra cualquiera de esa coletilla, distinguiremos a ese valor.
asi que por ejemplo "x". para la 3º respuesta.
como eliminacion, la clave para la 2º seria una que no fuera valida ni para la primera, ni para la tercera, asi que podra ser la "n" o la "o".
Asi tendriamos una combinacion de pregunta respuesta tal que (por ejemplo) "mel=x"
Que para que sirve esto? usad vuestra imaginacion! :D
Pensandolo un poco...creo que me ha quedado un poco fistro este texto, pero no tengo ganas de arreglarlo mas, ea, el que quiera, que me pregunte xD
Y para concluir, como hacian no mucho tiempo ha algunos buenos amigos, recomendacion musical!
"The Voice (Eimear Quinn)"
Saludos cordiales y hasta el proximo post!
pd. este panel de texto de blogger es un poco petardo con los estilos de texto a veces...
posted by Carlos GD @ 23:43
0 Comments:
Publicar un comentario
<< Home