Algorithmen - Mehrfachbaum

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Algorithmen - Mehrfachbaum

    Hi,

    hier meine Version des Mehrfachbaums...

    Datei: MultiNode.java

    Quellcode

    1. package U8;
    3. import java.util.Iterator;
    4. import java.util.LinkedList;
    6. /**
    7. * <p>
    8. * <b>Organisation:</b> FH-Wiesbaden<br>
    9. * <b>Homepage:</b> <a href="http://www.fh-wiesbaden.de">www.fh-wiesbaden.de</a><br>
    10. * <b>Fachbereich:</b> 06 - Meieninformatik<br>
    11. * </p>
    12. * <p>
    13. * <b>Entwickler:</b> Berntheisel, Stefan<br>
    14. * </p>
    15. * <p>
    16. * <b>Programm:</b><i> MultiNode </i><br>
    17. * </p>
    18. *
    19. * @author sbern001 (Username)
    20. * @version 1.0
    21. * @docRoot .
    22. */
    23. public class MultiNode {
    24. private char key;
    25. private LinkedList<MultiNode> SubNode = new LinkedList<MultiNode>();
    26. private String leaf;
    27. private int wordcounter = 1;
    29. // Konstruktor 1
    30. public MultiNode(char key) {
    31. this.key = key;
    32. }
    34. // Konstruktor 2
    35. public MultiNode(char key, String leaf) {
    36. this.key = key;
    37. this.leaf = leaf;
    38. }
    40. // Gibt den Wert des Schluessels zurueck
    41. public char getKey() {
    42. return key;
    43. }
    45. // Gibt den Wert des Blattes zurueck
    46. public String getLeaf() {
    47. return leaf;
    48. }
    50. // Setzt den Wert des Blattes
    51. public void setLeaf(String leaf) {
    52. this.leaf = leaf;
    53. }
    55. // Loescht das Blatt
    56. public void delLeaf() {
    57. this.leaf = null;
    58. this.wordcounter = 1;
    59. }
    61. // Gibt die Anzahl der Wort vorkommen zurueck
    62. public int getWordcounter() {
    63. return wordcounter;
    64. }
    66. // Legt die Anzahl der Wort wiederholungen fest
    67. public void setWordcounter(int wordcounter) {
    68. this.wordcounter = wordcounter;
    69. }
    71. // Erhoeht den Wort zaehler
    72. public void stepUpWordcounter() {
    73. this.wordcounter++;
    74. }
    76. // Fuegt neuen Knoten in die Liste
    77. public void addNode(MultiNode note) {
    78. SubNode.add(note);
    79. }
    81. // Prueft ob die Liste leer ist
    82. public boolean isNodeListEmpty () {
    83. return SubNode.isEmpty();
    84. }
    86. // Prueft ob der gesuchte Knoten in der Liste ist
    87. public boolean isNodeInList (char key) {
    88. MultiNode node = null;
    89. Iterator it = SubNode.iterator();
    90. while(it.hasNext()) {
    91. node = (MultiNode) it.next();
    92. if(node.getKey() == key)
    93. return true;
    94. }
    95. return false;
    96. }
    98. // Gibt den Knoten des gesuchten Schluessels zurueck
    99. public MultiNode findNode (char key) {
    100. MultiNode node = null;
    101. Iterator it = SubNode.iterator();
    102. while(it.hasNext()) {
    103. node = (MultiNode) it.next();
    104. if(node.getKey() == key)
    105. return node;
    106. }
    107. return node;
    108. }
    110. // Gibt alle vorhanden Schluessel zurueck
    111. public String findKeys () {
    112. String liste = "";
    113. int counter = 0;
    114. if(!isNodeListEmpty()) {
    115. MultiNode node = null;
    116. Iterator it = SubNode.iterator();
    117. while(it.hasNext()) {
    118. node = (MultiNode) it.next();
    119. liste += node.getKey();
    120. counter++;
    121. }
    122. }
    123. return liste;
    124. }
    125. }
    Alles anzeigen


    Datei: SearchTrie.java

    Quellcode

    1. package U8;
    3. import java.util.Iterator;
    4. import java.util.List;
    5. import java.util.LinkedList;
    7. /**
    8. * <p>
    9. * <b>Organisation:</b> FH-Wiesbaden<br>
    10. * <b>Homepage:</b> <a href="http://www.fh-wiesbaden.de">www.fh-wiesbaden.de</a><br>
    11. * <b>Fachbereich:</b> 06 - Meieninformatik<br>
    12. * </p>
    13. * <p>
    14. * <b>Entwickler:</b> Berntheisel, Stefan<br>
    15. * </p>
    16. * <p>
    17. * <b>Programm:</b><i> SearchTrie </i><br>
    18. * </p>
    19. *
    20. * @author sbern001 (Username)
    21. * @version 1.0
    22. * @docRoot .
    23. */
    25. public class SearchTrie implements STrie {
    26. private final char ROOT_PREFIX = '.';
    27. private final char MAIN_PREFIX = '.';
    28. private final boolean CASESENSITV;
    30. private MultiNode root = new MultiNode(ROOT_PREFIX);
    31. private int emptystring = 0;
    32. private int allwords = 0;
    33. private int words = 0;
    35. /**
    36. * Konstruktor
    37. * @param casesensitv true/false
    38. */
    39. SearchTrie(boolean casesensitv) {
    40. this.CASESENSITV = casesensitv;
    41. }
    43. /**
    44. * Gibt den aufbau des Mehrfachbaums auf der Console aus
    45. */
    46. public void showTree () {
    47. showTree(root, "");
    48. }
    50. /**
    51. * Gibt den aufbau des Mehrfachbaums auf der Console aus
    52. * @param node Knoten (nur fuer rekursiven Aufruf)
    53. * @param path aktueller Pfad (nur fuer rekursiven Aufruf)
    54. */
    55. private void showTree (MultiNode node, String path) {
    56. char keys[] = node.findKeys().toCharArray();
    57. char full_path[] = path.toCharArray();
    58. for(int i = 0; i < keys.length; i++) {
    59. String string_path = "";
    60. MultiNode t = node.findNode(keys[i]);
    61. for(int j = 0; j < full_path.length; j++)
    62. string_path += "(" + full_path[j] + ")" + "-->";
    63. if(t.getLeaf() != null) {
    64. System.out.printf("ROOT-->%s(%s) = %s (Anz: %d)\n", string_path, t.getKey(), t.getLeaf(), t.getWordcounter());
    65. }
    66. if(t.getLeaf() == null)
    67. showTree(t, path + keys[i]);
    68. }
    69. }
    71. /**
    72. * Gibt die Anzahl der leeren Strings zurueck
    73. * @return Anzahl leere Strings
    74. */
    75. public int getEmptyStrin () {
    76. return this.emptystring;
    77. }
    79. /**
    80. * Füge ein neues Wort in den Mehrfachbaum ein
    81. * @param s Wort
    82. */
    83. public void add(String s) {
    84. // Leer String kann nicht in den Baum eingefuegt werden
    85. if(s.equals("")) {
    86. emptystring++;
    87. return;
    88. }
    90. // Wandelt die Grossbuchstaben in Kleinbuchstaben
    91. if(CASESENSITV)
    92. s.toLowerCase();
    94. MultiNode node = root;
    95. char word[] = s.toCharArray();
    96. int counter = 0;
    98. // Die Schleife hangelt sich durch die Praefixe und vergleicht jeden Buchstabe
    99. // des neuen Wortes mit der in dem Baum erstellten Struktur. Wird eine Stelle gefunden,
    100. // an der das neue Wort vom vorhandenen Baum abweicht, so wurde die Stelle gefunden,
    101. // an der das neue Wort eingefuegt wird.
    103. while(counter <= word.length - 1 && !node.isNodeListEmpty() && node.isNodeInList(word[counter])) {
    104. node = node.findNode(word[counter]);
    105. counter++;
    107. // Prueft den aktuellen Knoten und schaut, ob das neue
    108. // Wort schon im Baum existiert. Wenn Ja, dann wird
    109. // die Anzahl um +1 erhoeht und abgebrochen.
    111. if(node.getLeaf() != null && node.getLeaf().equals(s)) {
    112. node.stepUpWordcounter();
    113. allwords++;
    114. return;
    115. }
    116. else if(node.isNodeInList(MAIN_PREFIX)) {
    117. MultiNode temp = node.findNode(MAIN_PREFIX);
    118. if(temp.getLeaf() != null && temp.getLeaf().equals(s)) {
    119. temp.stepUpWordcounter();
    120. allwords++;
    121. return;
    122. }
    123. }
    124. }
    126. // Wenn kein Blatt an dem aktuellen Knoten vorhanden ist, dann
    127. // kann das neue Wort an die aktuelle Stelle eingebunden werden.
    129. if(node.getLeaf() == null) {
    130. // 1. Fall
    131. // Wenn der aktuelle Knotenen den Schluessel des letzten Bruchstaben
    132. // des neuen Wortes hat, wird das neue Wort als Hauptpraefix eingefuegt.
    133. if(counter == s.length()) {
    134. MultiNode newWord = new MultiNode(MAIN_PREFIX);
    135. newWord.setLeaf(s);
    136. node.addNode(newWord);
    137. this.allwords++;
    138. this.words++;
    139. }
    140. // 2. Fall
    141. // Haengt an den aktuellen Schuessel das neue Wort
    142. else{
    143. MultiNode newWord = new MultiNode(word[counter]);
    144. newWord.setLeaf(s);
    145. node.addNode(newWord);
    146. this.allwords++;
    147. this.words++;
    148. }
    149. }
    150. else {
    151. // Speichern der Blatt informationen
    152. String temp_s = node.getLeaf();
    153. char temp_word[] = temp_s.toCharArray();
    154. int temp_wordcounter = node.getWordcounter();
    156. // Blatt loeschen
    157. node.delLeaf();
    159. // Praefix sollange erweitern bis neues Wort ungleich altes Wort ist
    160. while(counter <= s.length() - 1 && counter <= temp_s.length() - 1 && word[counter] == temp_word[counter]) {
    161. MultiNode temp = new MultiNode(word[counter]);
    162. node.addNode(temp);
    163. node = node.findNode(word[counter]);
    164. counter++;
    165. }
    168. MultiNode newWord;
    169. MultiNode newTempWord;
    171. if(counter == s.length() && counter < temp_s.length()) {
    172. newWord = new MultiNode(MAIN_PREFIX);
    173. newTempWord = new MultiNode(temp_word[counter]);
    174. this.allwords++;
    175. this.words++;
    176. }
    177. else if(counter == temp_s.length() && counter < s.length()) {
    178. newWord = new MultiNode(word[counter]);
    179. newTempWord = new MultiNode(MAIN_PREFIX);
    180. this.allwords++;
    181. this.words++;
    182. }
    183. else {
    184. newWord = new MultiNode(word[counter]);
    185. newTempWord = new MultiNode(temp_word[counter]);
    186. this.allwords++;
    187. this.words++;
    188. }
    190. newWord.setLeaf(s);
    191. newTempWord.setLeaf(temp_s);
    192. newTempWord.setWordcounter(temp_wordcounter);
    193. node.addNode(newWord);
    194. node.addNode(newTempWord);
    195. }
    196. }
    198. /**
    199. * Wie häufig kommt s vor?
    200. * @param s Wort
    201. * @return Häufigkeit Vorkommen
    202. */
    203. public int count(String s) {
    204. if(s == null || s.length() < 0 )
    205. return 0;
    206. if(s.equals(""))
    207. return emptystring;
    208. char word[] = s.toCharArray();
    209. int counter = 0;
    210. MultiNode node = root;
    211. while(counter < word.length - 1 && !node.isNodeListEmpty() && node.isNodeInList(word[counter])) {
    212. node = node.findNode(word[counter]);
    213. counter++;
    214. }
    215. if(node.getLeaf() != null && node.getLeaf().equals(s))
    216. return node.getWordcounter();
    217. if(node.isNodeInList(word[counter])) {
    218. node = node.findNode(word[counter]);
    219. if(node.getLeaf() != null && node.getLeaf().equals(s))
    220. return node.getWordcounter();
    221. if(node.isNodeInList(MAIN_PREFIX)) {
    222. node = node.findNode(MAIN_PREFIX);
    223. if(node.getLeaf() != null && node.getLeaf().equals(s))
    224. return node.getWordcounter();
    225. }
    226. }
    227. return 0;
    228. }
    231. /**
    232. * Entferne alle Vorkommen
    233. * @param s Wort
    234. * @return true gdw s mindestens einmal vorkam
    235. */
    237. public boolean remove(String s) {
    238. return false;
    239. }
    241. /**
    242. * Anzahl der Vorkommen aller Wörter
    243. * @return Anzahl alle Vorkommen
    244. */
    245. public int noOccurences() {
    246. return allwords;
    247. }
    249. /**
    250. * Anzahl der verschiedenen Wörter
    251. * @return Anzahl verschiedener Wörter
    252. */
    253. public int noWords() {
    254. return words;
    255. }
    257. /**
    258. * Iteriere über die vorkommenden Objekte
    259. * @return Iterator
    260. */
    261. public Iterator iterator() {
    262. return new Iterator() {
    263. private List<MultiNode> list = new LinkedList<MultiNode>();
    264. private Iterator it;
    265. private boolean buildIterator = false;
    267. private void buildIteratorArray() {
    268. buildIteratorArray(root);
    269. }
    271. private void buildIteratorArray(MultiNode node) {
    272. char keys[] = node.findKeys().toCharArray();
    273. for(int i = 0; i < keys.length; i++) {
    274. MultiNode t = node.findNode(keys[i]);
    275. if(t.getLeaf() != null) {
    276. list.add(t);
    277. }
    278. else
    279. buildIteratorArray(t);
    280. }
    281. }
    283. public boolean hasNext() {
    284. if(!buildIterator) {
    285. buildIteratorArray();
    286. it = list.iterator();
    287. buildIterator = true;
    288. }
    289. return it.hasNext();
    290. }
    292. public Object next() {
    293. MultiNode t = (MultiNode)it.next();
    294. return t.getLeaf();
    295. }
    297. public void remove() {
    298. // TODO Auto-generated method stub
    299. }
    300. };
    301. }
    302. }
    Alles anzeigen


    Datei: WordCount.java

    Quellcode

    1. package U8;
    3. import java.util.Map;
    4. import java.util.HashMap;
    5. import java.util.Iterator;
    6. import fhw.*;
    8. /**
    9. * @author Peter Barth
    10. * Testet die SearchList Implementierung
    11. * Einfach nur benutzen...
    12. */
    14. //--> geaenderte Version von sbern001
    16. public class WordCount {
    18. /**
    19. * @param args Dateinamen die zu verarbeiten sind
    20. */
    21. public static void main(String[] args) {
    22. String[] dateien =
    23. {
    24. "Woerter.txt",
    25. "AMidSummersNightDream.txt",
    26. "RomeoAndJuliet.txt",
    27. "words.txt"
    28. };
    29. if (args.length > 0)
    30. dateien = args;
    31. for (String datei : dateien) {
    32. test(datei, ADSTool.readStringArray("U8/" + datei));
    33. }
    34. }
    36. static String format = "%30s | %6s %6s | %10s | %10s | %10s | %10s\n";
    38. static String splitregex = "[ \t\n,:.]+";
    40. static boolean test(String name, String[] zeilen) {
    41. String anzahl, verschiedene, einfuegen, iterieren, zugriff, loeschen;
    42. int count = 0;
    43. SearchTrie sl = new SearchTrie(true); // Testet Ihre Implementierung
    44. Map hm = makeMap(zeilen); // Zum Gegentesten
    46. ADSTool.resetTime();
    47. for (int j = 0; j < zeilen.length; j++) {
    48. String[] woerter = zeilen[j].split(splitregex);
    49. for (int k = 0; k < woerter.length; k++) {
    50. // System.out.println(woerter[k]);
    51. sl.add(woerter[k]);
    52. count++;
    53. }
    54. }
    55. anzahl = Integer.toString(sl.noOccurences());
    56. verschiedene = Integer.toString(sl.noWords());
    58. sl.showTree(); // Zeigt die Struktur des Baums
    60. einfuegen = ADSTool.stringRTime();
    61. Iterator it = sl.iterator();
    62. count -= sl.getEmptyStrin();
    63. while (it.hasNext()) {
    64. String s = (String) it.next();
    65. int i = sl.count(s);
    66. count -= i;
    67. }
    68. iterieren = ADSTool.stringRTime();
    69. if (count != 0) {
    70. System.out.println("Fehler - Anzahl der Einträge " + count);
    71. return false;
    72. }
    73. it = hm.keySet().iterator();
    74. while (it.hasNext()) {
    75. String s = (String) it.next();
    76. int hmcount = ((Integer) hm.get(s)).intValue();
    77. if (hmcount != sl.count(s)) {
    78. System.err.println("Fehler - Anzahl der Vorkommen bei" + s);
    79. System.err.println(
    80. " Es sollten "
    81. + hmcount
    82. + " sein, sind aber "
    83. + sl.count(s));
    84. return false;
    85. }
    86. }
    87. zugriff = ADSTool.stringRTime();
    88. // it = hm.keySet().iterator();
    89. // while (it.hasNext()) {
    90. // String s = (String) it.next();
    91. // //.remove(
    92. // if (sl.count(s) != 0) {
    93. // System.err.println("Fehler - Element " + s + " nicht gelöscht");
    94. // return false;
    95. // }
    96. // }
    97. // if (sl.noOccurences() != 0 || sl.noWords() != 0) {
    98. // System.err.println("Fehler - Searchliste nicht leer");
    99. // return false;
    100. // }
    101. loeschen = ADSTool.stringRTime();
    102. System.out.format(format, "Name", "Worte", "Versch", "Einfügen", "Iterieren", "Zugriff", "Löschen");
    103. System.out.format(format, name, anzahl, verschiedene, einfuegen, iterieren, zugriff, loeschen);
    104. return true;
    105. }
    107. /**
    108. * Ein HashMap die dasselbe macht wie SearchList
    109. * wird nur zum Testen gemacht, kommt später noch
    110. * als Thema - nicht daran aufhalten...
    111. * @param zeilen Strings zum Hinzufügen
    112. * @return Map der Häufigkeiten
    113. */
    114. static Map<String, Integer> makeMap(String[] zeilen) {
    115. Map<String, Integer> hm = new HashMap<String, Integer>();
    116. for (int j = 0; j < zeilen.length; j++) {
    117. String[] woerter = zeilen[j].split(splitregex);
    119. for (int k = 0; k < woerter.length; k++) {
    120. if (hm.containsKey(woerter[k])) {
    121. int count = hm.get(woerter[k]);
    122. hm.put(woerter[k], count + 1);
    123. } else {
    124. hm.put(woerter[k], 1);
    125. }
    126. }
    127. }
    128. return hm;
    129. }
    131. }
    Alles anzeigen