matgreco
commented
4 years ago Hola Tomas,
Muy buenos tus comentarios. Estos provocarán cambios en el enunciado de la tarea, pero serán cosas que no deberían afectar el desarrollo. En general, las cosas que le agregan complejidad a esta tarea las vamos a obviar.
Iré punto a punto.
1.- Tu descripción es correcta. La ecuación será hasta w[l-1]*k^(l-1). Se actualizará el enunciado. 2.- No considerar el caso que existan colisiones. Si tienes un texto que aparezca una vez la palabra "or" e "it", simplemente tu arreglo en el índice 453 tendrá el valor 2. Si aparecen dos palabras que generan colisiones, simplemente considera que es la misma palabra. Se actualizará el enunciado. 3.- No es necesario eliminar caracteres de puntuación. Simplemente considera que "hola" es distinto a "hola,". 4.- Tu salida es correcta. En el ejemplo no se consideró que se produjeran colisiones. Ese ejemplo se actualizará. 5.- El 8 fue un error, en realidad era un 7. Respecto al ejemplo 2 tiene un error en que los hash presentados se calcularon con k=3. Será corregido ahora, tus cálculos están correctos. 6.- Ese problema no lo habíamos considerados y lo vamos a discutir hoy durante el día. Vamos a discutir la forma mas sencilla de abordar ese problema. Por lo pronto, considera que el arreglo es de tamaño un millón, y el numero asignado al índice de ese arreglo no debe sobrepasar ese rango.
Profesor, tengo las siguientes consultas con la tarea:
1) Según el enunciado: "Por cada palabra w de largo l, usted deberá calcular una función de hashing hash(w) la cual debe estar definida por la siguiente formula, donde w[0] corresponde al valor en ascii de la primera letra de la palabra w y k es un valor arbitrario definido por el usuario en el archivo de entrada.
hash(w, k) = w[0] ∗ k^0 + w[1] ∗ k^1 + w[2] ∗ k^2 + ... + w[l] ∗ k^l"
Dado que la palabra es de largo l, el último carácter de la palabra sería w[ l - 1] (descontando el carácter de termino de string '\0').
Se tendría: hash(w, k) = w[0] ∗ k^0 + w[1] ∗ k^1 + w[2] ∗ k^2 + ... + w[l-1] ∗ k^l-1"
Si se considera el carácter de término de string, que en ASCII es igual a cero, entonces la función queda igual que antes, ya que el carácter guardado en w[l] es igual a 0x00, o sea cero absoluto, no el carácter cero. w[l] * 0^l da cero.
Por tanto, estaría mal la fórmula.
2) Una vez calculado el hash, ¿hay que guardarlo como índice en el array A? Ejemplo: el hash de "or" es 453. Por ende, entiendo que en la posición 453 del array A se agrega un 1, simbolizando que hay un or. Si hubieran 2 "or", se suma 1 al valor anterior.
Con esta interpretación, en el ejemplo del pdf del lab, se genera una colisión en el caso de "or": hash(or, 3) = 453 hash(it, 3) = 453 Lo comprobé usando calculadora: "i" = 105 "t" = 116 -> 105 3^0 + 116 3^1 = 453.
A mí el resultado de "or" me da "453 2", debido a esta colisión. Supongo que este caso no estaba considerado.
3) Algunas palabras terminan en ".", "," (en el ejemplo 2 incluso hay corchetes: "reform.[48]") . Supongo que estos carácteres se tienen que eliminar. Yo lo hice así al menos (nota: como que esto le sigue agregando más complejidad a la tarea).
4) Considerando el detalle descrito en el punto anterior a mí me dan otros valores: 3 It is a long established fact that a reader will be distracted by the readable content of a page when looking at its layout. The point of using Lorem Ipsum is that it has a more-or-less normal distribution of letters, as opposed to using Content here, content here, making it look like readable English. 6 or a Content content hola that
La salida presentada en el PDF es: 453 1 97 3 123997 1 124029 1 4028 0 4433 2
A mí me dan:
or 453 2 (Colisión) a 97 4 (En el texto hay 4 "a" no 3) Content 123997 1 (OK) content 124029 2 (En el texto hay 2 "content") hola 4028 0 (OK) that 4433 2 (OK)
5) En el ejemplo 2 del repositorio, sólo coinciden las palabras que no están en el texto pero no sus hash (nótese además que en la tercera línea hay un 8 pero despúes siguen sólo 7 palabras): 5 During the late 19th century and the early 20th century, social democracy was a broad labour movement within socialism that aimed to replace private ownership with social ownership of the means of production, distribution and exchange, taking influence from both Marxism and the supporters of Ferdinand Lassalle. By 1868–1869, the socialism associated with Karl Marx had become the official theoretical basis of the first social democratic party established in Europe, the Social Democratic Workers' Party of Germany. By the early 20th century, the German social democratic politician Eduard Bernstein rejected the ideas in orthodox Marxism that proposed specific historical progression and revolution as a means to achieve social equality, advancing the position that socialism should be grounded in ethical and moral arguments for social justice and egalitarianism that are to be achieved through gradual legislative reform.[48] Following the split between reformist and revolutionary socialists in the Second International, socialist parties influenced by Bernstein rejected revolutionary politics in favour of parliamentary reform while remaining committed to socialization. During the 1920s and 1930s, social democracy became a dominant tendency within the socialist movement, mainly associated with reformist socialism whilst communism represented revolutionary socialism.[49] Under the influence of politicians like Carlo Rosselli in Italy, social democrats began disassociating themselves from orthodox Marxism altogether as represented by Marxism–Leninism,[50] embracing liberal socialism,[51] Keynesianism[50] and appealing to morality rather than any consistent systematic, scientific or materialist worldview.[52] Social democracy made appeals to communitarian, corporatist and sometimes nationalist sentiments while rejecting the economic and technological determinism generally characteristic of both orthodox Marxism and economic liberalism. Social democracy influenced the development of social corporatism, a form of economic tripartite corporatism based upon a social partnership between the interests of capital and labour, involving collective bargaining between representatives of employers and of labour mediated by the government at the national level.[54] During the post-war consensus, this form of social democracy has been a major component of the Nordic model and to a lesser degree the West European social market economies.[55] The development of social corporatism began in Norway and Sweden in the 1930s and was consolidated in the 1960s and 1970s.[56] The system was based upon the dual compromise of capital and the labour as one component and the market and the state as the other component. By the post-World War II period and its economic consensus and expansion, most social democrats in Europe had abandoned their ideological connection to orthodox Marxism and shifted their emphasis toward social policy reform as a compromise between capitalism to socialism.[57] During the Third Way development of social democracy, social democrats adjusted to the political climate since the 1980s that favoured capitalism by recognising that outspoken opposition to capitalism in these circumstances was politically nonviable and that accepting capitalism as the current powers that be and seeking to administer it to challenge free-market and laissez-faire capitalism was a more pressing immediate concern.[58] The Third Way stands for a modernized social democracy,[59] but the social democracy that remained committed to the gradual abolition of capitalism, along with social democrats opposed to the Third Way, merged into democratic socialism.[60] Although social democracy originated as a revolutionary socialist or communist movement,[19] one dinstinction made to separate democratic socialism and social democracy is that the former can include revolutionary means[61][62] while the latter asserts that the only acceptable constitutional form of government is representative democracy under the In certain contexts, the Anti-Defamation League categorizes the phrase as a hate symbol and describes it as "a slogan of long standing in the skinhead culture," while noting the phrase is used both by racist and anti-racist skinheads. The acronym is often integrated into prison tattoos in the United Kingdom, commonly rendered as one letter per finger, alternatively sometimes seen as symbolic small dots across each knuckle. 8 mainly politician ide 1999 good-job revolutionary first
La salida presentada es: 42466 1 3142516 1 1314 0 2272 0 328783 0 93476127 5 13944 1
A mí me da: mainly 462594 1 (comprobado con calculadora) palabra politician muy grande para el computador. (Ver punto 6 de este issue) ide 3130 0 (comprobado con calculadora) 1999 8884 0 (comprobado con calculadora) palabra good-job muy grande para el computador. (Ver punto 6 de este issue) palabra revolutionary muy grande para el computador. (Ver punto 6 de este issue) first 90352 1 (comprobado con calculadora)
6) Con la interpretación que le di a la tarea, algunas palabras no las puedo insertar en el array A, porque da un hash muy grande:
politician 262901492. revolutionary 1963618451
Es imposible crear un array con esos índices. Habría que crear otra función hash no descrita en el enunciado de la tarea.
Nota: Hasta tuve que crear la variable que guarda el hash como "unsigned long int" para que el compilador me deje guardar el resultado.
Gracias por su ayuda.