Foros del Web » Programando para Internet » PHP »

Ayuda Urgente

Estas en el tema de Ayuda Urgente en el foro de PHP en Foros del Web. Hola : Necesito de si valioza ayuda nuevamente Tengo el siguiente problema: El problema consiste en hacer un programa de búsqueda. El algoritmo consiste en ...
  #1 (permalink)  
Antiguo 08/09/2004, 12:41
 
Fecha de Ingreso: julio-2002
Ubicación: Rancagua - Chile
Mensajes: 494
Antigüedad: 15 años, 5 meses
Puntos: 0
Ayuda Urgente

Hola :
Necesito de si valioza ayuda nuevamente
Tengo el siguiente problema:
El problema consiste en hacer un programa de búsqueda.
El algoritmo consiste en dar un peso a la cantidad de veces que una palabra aparece en el
string de búsqueda y en el documento a buscar.
Se entregará un string de búsqueda seguido de un set de documentos. Tendrás que
calcular el puntaje para cada documento y guardarlo en el archivo de salida, en el mismo
orden en que aparece en el archivo de entrada.
Para calcular el puntaje de un documento tienes que calcular primero el puntaje de una
palabra para cada palabra que aparece en el string de búsqueda. El puntaje de una palabra
es la cantidad de veces que aparece ese palabra en el string de búsqueda multiplicado por
la cantidad de veces que aparece en el documento. El puntaje del documento es la suma
de las raíces cuadradas de cada puntaje de la palabra.
El programa debe estar escrito en PHP.
Formato de entrada
El archive de entrada se llamará “input.txt” y consiste en un set de documentos separados
por una línea que contiene sólo 10 guiones, “----------“. Ninguna línea tendrá más de 250
caracteres. Ningún documento tendrá más de 100 líneas. El primer documento es el string
de búsqueda. El archivo termina con dos líneas seguidas con diez guiones cada una.
Los documentos pueden usar cualquier carácter ASCII. Tienes que parsear cada
documento en un set de palabras.
Las palabras están separadas por espacio en el documento de entrada. Las comparaciones
entre palabras son case-insensitive. Las puntuaciones deben ser removidas antes de la
comparación, por ejemplo “O’higgins” queda “Ohiggins”. Las palabras resultantes sólo
deben contener los caracteres {[a-z],[0-9]}. Una palabra que consista sólo de
puntuaciones debe ser ignorada. Puedes asumir que el string de búsqueda y cada
documento contienen al menos una palabra válida.
Formato de salida
La salida consiste en una serie de puntajes, uno por línea, con dos decimales. Los
puntajes son impresos en el orden en que vienen los documentos en la entrada. Ningún
otro carácter puede aparecer en la salida. El archivo debe llamarse “output.txt”. No debe
mostrarse nada en pantalla.
Los archivos de entrada y salida deben estar en el mismo directorio donde se ejecute el
script.

Mi problema mas grande es que no he trabajo con archivos, entonces no se como manejarlos, digamos linea por linea o registro por registro (BD).
El segundo gran problema es que, dado que estoy sin trabajo, me lo pidieron en una entrevista de trabajo y tengo que hacerlo lo mas pronto posible.

Ojala me puedan ayudar y tal vez poder conseguir el trabajo.

Gracias.

Salu2 !!!
__________________
AK.T.I.V.E.tm Live, Never DIE
  #2 (permalink)  
Antiguo 09/09/2004, 07:53
 
Fecha de Ingreso: julio-2002
Ubicación: Rancagua - Chile
Mensajes: 494
Antigüedad: 15 años, 5 meses
Puntos: 0
Código PHP:
/* se abre el archivo */
  
$fp fopen ("input.txt""r");
  while (!
feof ($fp)){
     
/*se obtiene la linea */
     
$linea fgets($fp4096);
     
$arreglo split(" "$linea);

     for (
$i 0$i count($arreglo); $i++){
        print 
$arreglo[$i];
     }
  } 
eso es lo que tengo, estoy imprimiendo cada palabra que este separada por un espacio en blanco, pero quiero poder capturar la primera linea del archivo que esta en $linea y esa me retornara todos los string que debo buscar dentro del archivo, pero ahora necesito separarlos y guardarlos en un arreglo, para poder hacer la busqueda con cada elemento del arreglo dentro del archivo.

Espero me puedan ayudar.

Gracias.

Salu2 !!!
__________________
AK.T.I.V.E.tm Live, Never DIE
  #3 (permalink)  
Antiguo 09/09/2004, 09:07
Ex Colaborador
 
Fecha de Ingreso: junio-2002
Mensajes: 9.091
Antigüedad: 15 años, 6 meses
Puntos: 16
Hola,

Bueno, si el espacio en memoria no es problema, podrias usar file() (www.php.net/file) para leer todo el fichero en un array donde cada elemento del array es una linea del fichero. Creo que es mas facil recorrer un array que ir recorriendo el fichero poco a poco.

¿Has hecho ya el pseudocodigo de la aplicacion? Ya sabes, ir dividiendo el problema en pasos mas pequeños que pueden ser realizados por una funcion. Por cierto, ¿tienes que hacerlo con OOP o vale con funciones? (mas que nada, porque si lo haces con OOP y no sabes OOP pues no es plan).

Saludos.

PD: Luego cuando tenga un hueco hago un esbozo de como podria ser el programa.
__________________
Josemi

Aprendiz de mucho, maestro de poco.
  #4 (permalink)  
Antiguo 09/09/2004, 09:27
 
Fecha de Ingreso: julio-2002
Ubicación: Rancagua - Chile
Mensajes: 494
Antigüedad: 15 años, 5 meses
Puntos: 0
el espacio no es drama y no utilizo OOP.
Pero como bien dices, tendria todas las lineas del archivo en un array (arreglo1), pero debo tomar la primera posición o la primera linea y separar cada palabra y guardarla en otro array (arreglo2), de forma de poder tomar cada una de las palabras del arreglo2 y contar cuantas veces aparece dentro del archivo completo, y cada una de esas cantidades sacarle su raiz cuadrada y acumularlas.
Luego guardo las cantidades de veces que aparecen cada palabra, y la suma de las raices cuadradas.


Eso.

Gracias.


Salu2 !!!
__________________
AK.T.I.V.E.tm Live, Never DIE
  #5 (permalink)  
Antiguo 09/09/2004, 15:39
 
Fecha de Ingreso: julio-2002
Ubicación: Rancagua - Chile
Mensajes: 494
Antigüedad: 15 años, 5 meses
Puntos: 0
Alguien me puede decir como tomar un elemento de un Array (que en este caso es un string), que esta separado por espacios, tomar cada palabra y guardarla en otro arreglo

Gracias.

Salu2 !!!
__________________
AK.T.I.V.E.tm Live, Never DIE
  #6 (permalink)  
Antiguo 09/09/2004, 15:58
Avatar de jpinedo
Colaborador
 
Fecha de Ingreso: septiembre-2003
Ubicación: Lima, Perú
Mensajes: 3.120
Antigüedad: 14 años, 2 meses
Puntos: 41
Para eso se utiliza la función explode()
Código PHP:
$elemento "cadena separada por espacios";
$otro_array explode(' '$elemento);
echo 
"<pre>";
print_r($otro_array);
echo 
"</pre>"
Saludos
  #7 (permalink)  
Antiguo 10/09/2004, 02:41
Ex Colaborador
 
Fecha de Ingreso: junio-2002
Mensajes: 9.091
Antigüedad: 15 años, 6 meses
Puntos: 16
Bueno, aqui va mi esbozo de aplicacion. Lee las notas finales.

Primero hagamos el pseudocodigo:
Código:
Abrir Entrada
Leer Primer Documento
Calcular terminos de busqueda y sus puntos
Inicializar Resultado
Mientras Leer Documento devuelva un documento
  Calcular terminos del documento y sus puntos
  Calcular puntuacion del documento y guardarlo
Fin mientras
Guardar resultado en fichero
El codigo PHP seria algo como:
Código PHP:
$input=file('input.txt');
$busqueda=leerDocumento($input);
$terminosBusqueda=array();
$terminosBusqueda=calcularTerminos($busqueda);
$resultado=array();
while (
false!=($documento=leerDocumento($input))) {
    
$terminosDoc=array();
    
$terminosDoc=calcularTerminos($documento);
    
$resultado[]=round(calcularPuntuacionDoc($terminosBusqueda,$terminosDoc),2);
}
$fo=fopen('output.txt','w');
fwrite($fo,join("\n",$resultado)); // en lugar de \n podria ser \r\n, dependiendo del SO
fclose($fo); 
Bien, ahora toca a las funciones. Empecemos por leerDocumento(). Le pasamos el array con toda la entrada. Devuelve un array con las lineas correspondientes a un documento. Lleva un puntero interno que almacena el indice de la linea que toca leer. Se van leyendo lineas hasta que encuentras la cadena de fin de documento. Si el documento tiene 0 lineas, se devuelve false, porque se ha llegado al final del fichero (2 "fin de documentos" seguidos).

En pseudo codigo:
Código:
Mientras Linea actual sea distinta a FinDocumento
  Añadir Linea actual a documento
  Mover a siguiente Linea
Fin mientras
Mover a siguiente linea // para apuntar a la siguiente de FinDocumento
Si documento no tiene lineas devolver false (no mas documentos)
Devolver documento
Y lo implementamos usando static para la variable que lleva el puntero:
Código PHP:
function leerDocumento($entrada) {
    static 
$indice=0;
    if (
$indice>=count($entrada)) return false;  // si el puntero apunta mas alla del ultimo elemento, devolvemos false
    
$fd='----------';  // cadena Fin de Documento
    
$doc=array();  // inicializamos el documento
    
while ($fd!=trim($entrada[$indice])) { // usamos trim() para quitar el salto de linea (file() los deja)
        
$doc[]=$entrada[$indice];
        
$indice++;
    }
    
$indice++;
    if (
0==count($doc)) return false;  // no mas documentos
    
return $doc;

Pasamos a calcularTerminos(), recibe un documento y devuelve un array asociativo, cuyos indices son las palabras y los valores el numero de repeticiones. En pseudocodigo:
Código:
Inicializar lista terminos
Para cada linea del documento
  Sacamos un array con las palabras de la linea
  Para cada palabra
    Normalizamos la palabra
    Si la palabra normalizada no esta en la lista terminos
      Añadir a la lista con valor 1
    sino
      Incrementar el valor del termino en la lista
    Fin si
  Fin Para
Fin Para
Devolver Lista terminos
Implementado en PHP:
Código PHP:
function calcularTerminos($doc) {
    
$listaTerminos=array();
    foreach (
$doc as $linea) {
        
$terminos=explode(' ',$linea);
        foreach (
$terminos as $termino) {
            
$terminoNormalizado=normalizarTermino($termino);
            if (
''!=$terminoNormalizado) {
                if (isset(
$listaTerminos[$terminoNormalizado])) {
                    
$listaTerminos[$terminoNormalizado]++;
                } else {
                    
$listaTerminos[$terminoNormalizado]=1;
                }
            }
        }
    }
    return 
$listaTerminos;

normalizarTermino() se encarga de pasar cada termino al formato que te dicen, sin signos de puntuacion. Ademas, pasa el termino a minusculas, porque quieren que la comparacion sea case-insensitive. El codigo es auto explicativo:
Código PHP:
function normalizarTermino($palabra) {
    
$palabra=strtolower(trim($palabra));
    
$palabra=ereg_replace("[^a-z0-9]",'',$palabra);
    return 
$palabra;

OJO, no estoy seguro de la expresion regular, no son mi fuerte. Y a pesar de ser la mas sencilla, es la mas problematica. ¿Por que? Por el idioma. strtolower() puede no reconocer la Ñ y vocales acentuadas (y quizas Ç) como mayusculas y no pasarlas a minusculas. Y esos caracteres no estan en el intervalo a-z para los ingleses, asi que el ereg_replace() los eliminaria. Puedes buscar una solucion a eso (poner en minusculas "a mano" con strtr() y añadirlos en ereg_replace) o plantearlo asi, indicando el problema.

¿Que queda? Ya, calcularPuntuacionDoc(). Recibe 2 arrays con los terminos de busqueda y los del documento. La puntuacion es la suma de las raices cuadradas del producto de las repeticiones del termino. Creo que el codigo tambien es bastante directo:
Código PHP:
function calcularPuntuacionDoc($busq$doc) {
    
$puntuacion=0;
    foreach (
$busq as $termino => $puntBusq) {
        if (isset(
$doc[$termino])) {
            
$puntuacion+=sqrt($puntBusq*$doc[$termino]);
        }
    }
    return 
$puntacion;

Creo que esta claro: para cada termino de busqueda, miras si esta en en el documento y si esta, hayas el producto y calculas la raiz cuadrada. Si la palabra no esta en la lista de terminos de busqueda, o no esta en el documento, el producto siempre sera 0. La raiz cuadrada de 0 es 0. Asi que para la puntuacion del documento solo la calculas con los terminos que esten tanto en la busqueda como en el documento.

Y creo que ya esta todo.
ATENCION, el codigo no esta probado, lo he sacado directamente de mi cabeza. Puede tener errores. Lo ideal seria que tuviese un fichero de entrada de ejemplo con su salida correcta, para probar este codigo y comprobar que funciona (se hace asi siempre). OJO, tampoco he puesto controles de errores, como validacion de parametros y cosas asi.

Espero que te sirva de guia.
__________________
Josemi

Aprendiz de mucho, maestro de poco.

Última edición por josemi; 10/09/2004 a las 02:43
  #8 (permalink)  
Antiguo 11/09/2004, 13:59
 
Fecha de Ingreso: julio-2002
Ubicación: Rancagua - Chile
Mensajes: 494
Antigüedad: 15 años, 5 meses
Puntos: 0
Gracias, Muchas Gracias.


Salu2 !!!
__________________
AK.T.I.V.E.tm Live, Never DIE
Atención: Estás leyendo un tema que no tiene actividad desde hace más de 6 MESES, te recomendamos abrir un Nuevo tema en lugar de responder al actual.
Respuesta

SíEste tema le ha gustado a 1 personas




La zona horaria es GMT -6. Ahora son las 03:09.