code_junkie

Word Anagram Hashing Algorithm?

Nov 13th, 2011
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.64 KB | None | 0 0
  1. man car kile arc none like
  2.  
  3. man
  4. car arc
  5. kile like
  6. none
  7.  
  8. string line = Console.ReadLine();
  9. string []words=line.Split(' ');
  10. int[] numbers = GetUniqueInts(words);
  11. for (int i = 0; i < words.Length; i++)
  12. {
  13. if (table.ContainsKey(numbers[i]))
  14. {
  15. table[numbers[i]] = table[numbers[i]].Append(words[i]);
  16. }
  17. else
  18. {
  19. table.Add(numbers[i],new StringBuilder(words[i]));
  20. }
  21.  
  22. }
  23.  
  24. using System;
  25. using System.Collections.Generic;
  26. using System.Linq;
  27.  
  28. class FindAnagrams
  29. {
  30. static void Main(string[] args)
  31. {
  32. var lookup = args.ToLookup(word => SortLetters(word));
  33.  
  34. foreach (var entry in lookup)
  35. {
  36. foreach (var word in entry)
  37. {
  38. Console.Write(word);
  39. Console.Write(" ");
  40. }
  41. Console.WriteLine();
  42. }
  43. }
  44.  
  45. static string SortLetters(string original)
  46. {
  47. char[] letters = original.ToCharArray();
  48. Array.Sort(letters);
  49. return new string(letters);
  50. }
  51. }
  52.  
  53. c:UsersJonTest>FindAnagrams.exe man car kile arc none like
  54. man
  55. car arc
  56. kile like
  57. none
  58.  
  59. primes = [2, 41, 37, 47, 3, 67, 71, 23, 5, 101, 61, 17, 19, 13, 31, 43, 97, 29, 11, 7, 73, 83, 79, 89, 59, 53]
  60.  
  61.  
  62. def get_frequency_map(word):
  63. map = {}
  64.  
  65. for letter in word:
  66. map[letter] = map.get(letter, 0) + 1
  67.  
  68. return map
  69.  
  70.  
  71. def hash(word):
  72. map = get_frequency_map(word)
  73. product = 1
  74. for letter in map.iterkeys():
  75. product = product * primes[ord(letter)-97] ** map.get(letter, 0)
  76. return product
  77.  
  78. from collections import defaultdict
  79. res = defaultdict(list)
  80. L = "car, acr, bat, tab, get, cat".split(", ")
  81.  
  82. for w in L:
  83. res["".join(sorted(w))].append(w)
  84.  
  85. print(res.values())
  86.  
  87. unsigned char letter_frequency[26];
  88.  
  89. def processword(word, downcase)
  90. word.chomp!
  91. word.squeeze!(" ")
  92. word.chomp!(" ")
  93. if (downcase)
  94. word.downcase!
  95. end
  96. if ($dict[word]==nil)
  97. stdword=word.downcase
  98. signature=$letters.collect {|letter| stdword.count(letter)}
  99. signature.each do |cnt|
  100. if (cnt>9)
  101. puts "Signature overflow:#{word}|#{signature}|#{cnt}"
  102. end
  103. end
  104. $dict[word]=[$wordid,signature]
  105. $wordid=$wordid+1
  106. end
  107. end
  108.  
  109. #define BUCKETS 49999
  110.  
  111. struct bucket {
  112. char *word;
  113. struct bucket *next;
  114. };
  115.  
  116. static struct bucket hash_table[BUCKETS];
  117.  
  118. static unsigned int hash_word(char *word)
  119. {
  120. char *p = word;
  121. unsigned int hash = 0;
  122.  
  123. while (*p) {
  124. if (*p < 97 || *p > 122) {
  125. return 0;
  126. }
  127. hash |= 2 << (*p - 97);
  128. *p++;
  129. }
  130.  
  131. return hash % BUCKETS;
  132. }
  133.  
  134. public static HashMap<String, Integer> getHashMap(String word) {
  135. HashMap<String, Integer> map = new HashMap<String, Integer>();
  136. String[] chars = word.split("");
  137. int index = 0;
  138. for (String c : chars) {
  139. map.put(c, index);
  140. index++;
  141. }
  142. return map;
  143. }
  144.  
  145. public static int alphaHash(String word, int base,
  146. HashMap<String, Integer> map) {
  147. String[] chars = word.split("");
  148. int result = 0;
  149. for (String c : chars) {
  150. if (c.length() <= 0 || c.equals(null)) {
  151. continue;
  152. }
  153. int index = 0;
  154. if (map.containsKey(c)) {
  155. index = map.get(c);
  156. } else {
  157. index = Integer.MAX_VALUE;
  158. }
  159. result += index;
  160. if (result > base) {
  161. return result;
  162. }
  163. }
  164. return result;
  165. }
  166.  
  167. HashMap<String, Integer> map = getHashMap(sample);
  168. int sampleHash = alphaHash(sample, Integer.MAX_VALUE, map);
  169. for (String s : args) {
  170. if (sampleHash == alphaHash(s, sampleHash, map)) {
  171. System.out.print(s + " ");
  172. }
  173. }
  174.  
  175. // structured for clarity
  176. static bool isAnagram(String s1, String s2)
  177. {
  178. int[] histogram = new int[256];
  179.  
  180. int uniques = 0;
  181.  
  182. // scan first string
  183. foreach (int c in s1)
  184. {
  185. // count occurrence
  186. int count = ++histogram[c];
  187.  
  188. // count uniques
  189. if (count == 1)
  190. {
  191. ++uniques;
  192. }
  193. }
  194.  
  195. // scan second string
  196. foreach (int c in s2)
  197. {
  198. // reverse count occurrence
  199. int count = --histogram[c];
  200.  
  201. // reverse count uniques
  202. if (count == 0)
  203. {
  204. --uniques;
  205. }
  206. else if (count < 0) // trivial reject of longer strings or more occurrences
  207. {
  208. return false;
  209. }
  210. }
  211.  
  212. // final histogram unique count should be 0
  213. return (uniques == 0);
  214. }
Add Comment
Please, Sign In to add comment