Hi,
hier meine Version des Mehrfachbaums...
Datei: MultiNode.java
Alles anzeigen
Datei: SearchTrie.java
Alles anzeigen
Datei: WordCount.java
Alles anzeigen
hier meine Version des Mehrfachbaums...
Datei: MultiNode.java
Quellcode
- package U8;
- import java.util.Iterator;
- import java.util.LinkedList;
- /**
- * <p>
- * <b>Organisation:</b> FH-Wiesbaden<br>
- * <b>Homepage:</b> <a href="http://www.fh-wiesbaden.de">www.fh-wiesbaden.de</a><br>
- * <b>Fachbereich:</b> 06 - Meieninformatik<br>
- * </p>
- * <p>
- * <b>Entwickler:</b> Berntheisel, Stefan<br>
- * </p>
- * <p>
- * <b>Programm:</b><i> MultiNode </i><br>
- * </p>
- *
- * @author sbern001 (Username)
- * @version 1.0
- * @docRoot .
- */
- public class MultiNode {
- private char key;
- private LinkedList<MultiNode> SubNode = new LinkedList<MultiNode>();
- private String leaf;
- private int wordcounter = 1;
- // Konstruktor 1
- public MultiNode(char key) {
- this.key = key;
- }
- // Konstruktor 2
- public MultiNode(char key, String leaf) {
- this.key = key;
- this.leaf = leaf;
- }
- // Gibt den Wert des Schluessels zurueck
- public char getKey() {
- return key;
- }
- // Gibt den Wert des Blattes zurueck
- public String getLeaf() {
- return leaf;
- }
- // Setzt den Wert des Blattes
- public void setLeaf(String leaf) {
- this.leaf = leaf;
- }
- // Loescht das Blatt
- public void delLeaf() {
- this.leaf = null;
- this.wordcounter = 1;
- }
- // Gibt die Anzahl der Wort vorkommen zurueck
- public int getWordcounter() {
- return wordcounter;
- }
- // Legt die Anzahl der Wort wiederholungen fest
- public void setWordcounter(int wordcounter) {
- this.wordcounter = wordcounter;
- }
- // Erhoeht den Wort zaehler
- public void stepUpWordcounter() {
- this.wordcounter++;
- }
- // Fuegt neuen Knoten in die Liste
- public void addNode(MultiNode note) {
- SubNode.add(note);
- }
- // Prueft ob die Liste leer ist
- public boolean isNodeListEmpty () {
- return SubNode.isEmpty();
- }
- // Prueft ob der gesuchte Knoten in der Liste ist
- public boolean isNodeInList (char key) {
- MultiNode node = null;
- Iterator it = SubNode.iterator();
- while(it.hasNext()) {
- node = (MultiNode) it.next();
- if(node.getKey() == key)
- return true;
- }
- return false;
- }
- // Gibt den Knoten des gesuchten Schluessels zurueck
- public MultiNode findNode (char key) {
- MultiNode node = null;
- Iterator it = SubNode.iterator();
- while(it.hasNext()) {
- node = (MultiNode) it.next();
- if(node.getKey() == key)
- return node;
- }
- return node;
- }
- // Gibt alle vorhanden Schluessel zurueck
- public String findKeys () {
- String liste = "";
- int counter = 0;
- if(!isNodeListEmpty()) {
- MultiNode node = null;
- Iterator it = SubNode.iterator();
- while(it.hasNext()) {
- node = (MultiNode) it.next();
- liste += node.getKey();
- counter++;
- }
- }
- return liste;
- }
- }
Datei: SearchTrie.java
Quellcode
- package U8;
- import java.util.Iterator;
- import java.util.List;
- import java.util.LinkedList;
- /**
- * <p>
- * <b>Organisation:</b> FH-Wiesbaden<br>
- * <b>Homepage:</b> <a href="http://www.fh-wiesbaden.de">www.fh-wiesbaden.de</a><br>
- * <b>Fachbereich:</b> 06 - Meieninformatik<br>
- * </p>
- * <p>
- * <b>Entwickler:</b> Berntheisel, Stefan<br>
- * </p>
- * <p>
- * <b>Programm:</b><i> SearchTrie </i><br>
- * </p>
- *
- * @author sbern001 (Username)
- * @version 1.0
- * @docRoot .
- */
- public class SearchTrie implements STrie {
- private final char ROOT_PREFIX = '.';
- private final char MAIN_PREFIX = '.';
- private final boolean CASESENSITV;
- private MultiNode root = new MultiNode(ROOT_PREFIX);
- private int emptystring = 0;
- private int allwords = 0;
- private int words = 0;
- /**
- * Konstruktor
- * @param casesensitv true/false
- */
- SearchTrie(boolean casesensitv) {
- this.CASESENSITV = casesensitv;
- }
- /**
- * Gibt den aufbau des Mehrfachbaums auf der Console aus
- */
- public void showTree () {
- showTree(root, "");
- }
- /**
- * Gibt den aufbau des Mehrfachbaums auf der Console aus
- * @param node Knoten (nur fuer rekursiven Aufruf)
- * @param path aktueller Pfad (nur fuer rekursiven Aufruf)
- */
- private void showTree (MultiNode node, String path) {
- char keys[] = node.findKeys().toCharArray();
- char full_path[] = path.toCharArray();
- for(int i = 0; i < keys.length; i++) {
- String string_path = "";
- MultiNode t = node.findNode(keys[i]);
- for(int j = 0; j < full_path.length; j++)
- string_path += "(" + full_path[j] + ")" + "-->";
- if(t.getLeaf() != null) {
- System.out.printf("ROOT-->%s(%s) = %s (Anz: %d)\n", string_path, t.getKey(), t.getLeaf(), t.getWordcounter());
- }
- if(t.getLeaf() == null)
- showTree(t, path + keys[i]);
- }
- }
- /**
- * Gibt die Anzahl der leeren Strings zurueck
- * @return Anzahl leere Strings
- */
- public int getEmptyStrin () {
- return this.emptystring;
- }
- /**
- * Füge ein neues Wort in den Mehrfachbaum ein
- * @param s Wort
- */
- public void add(String s) {
- // Leer String kann nicht in den Baum eingefuegt werden
- if(s.equals("")) {
- emptystring++;
- return;
- }
- // Wandelt die Grossbuchstaben in Kleinbuchstaben
- if(CASESENSITV)
- s.toLowerCase();
- MultiNode node = root;
- char word[] = s.toCharArray();
- int counter = 0;
- // Die Schleife hangelt sich durch die Praefixe und vergleicht jeden Buchstabe
- // des neuen Wortes mit der in dem Baum erstellten Struktur. Wird eine Stelle gefunden,
- // an der das neue Wort vom vorhandenen Baum abweicht, so wurde die Stelle gefunden,
- // an der das neue Wort eingefuegt wird.
- while(counter <= word.length - 1 && !node.isNodeListEmpty() && node.isNodeInList(word[counter])) {
- node = node.findNode(word[counter]);
- counter++;
- // Prueft den aktuellen Knoten und schaut, ob das neue
- // Wort schon im Baum existiert. Wenn Ja, dann wird
- // die Anzahl um +1 erhoeht und abgebrochen.
- if(node.getLeaf() != null && node.getLeaf().equals(s)) {
- node.stepUpWordcounter();
- allwords++;
- return;
- }
- else if(node.isNodeInList(MAIN_PREFIX)) {
- MultiNode temp = node.findNode(MAIN_PREFIX);
- if(temp.getLeaf() != null && temp.getLeaf().equals(s)) {
- temp.stepUpWordcounter();
- allwords++;
- return;
- }
- }
- }
- // Wenn kein Blatt an dem aktuellen Knoten vorhanden ist, dann
- // kann das neue Wort an die aktuelle Stelle eingebunden werden.
- if(node.getLeaf() == null) {
- // 1. Fall
- // Wenn der aktuelle Knotenen den Schluessel des letzten Bruchstaben
- // des neuen Wortes hat, wird das neue Wort als Hauptpraefix eingefuegt.
- if(counter == s.length()) {
- MultiNode newWord = new MultiNode(MAIN_PREFIX);
- newWord.setLeaf(s);
- node.addNode(newWord);
- this.allwords++;
- this.words++;
- }
- // 2. Fall
- // Haengt an den aktuellen Schuessel das neue Wort
- else{
- MultiNode newWord = new MultiNode(word[counter]);
- newWord.setLeaf(s);
- node.addNode(newWord);
- this.allwords++;
- this.words++;
- }
- }
- else {
- // Speichern der Blatt informationen
- String temp_s = node.getLeaf();
- char temp_word[] = temp_s.toCharArray();
- int temp_wordcounter = node.getWordcounter();
- // Blatt loeschen
- node.delLeaf();
- // Praefix sollange erweitern bis neues Wort ungleich altes Wort ist
- while(counter <= s.length() - 1 && counter <= temp_s.length() - 1 && word[counter] == temp_word[counter]) {
- MultiNode temp = new MultiNode(word[counter]);
- node.addNode(temp);
- node = node.findNode(word[counter]);
- counter++;
- }
- MultiNode newWord;
- MultiNode newTempWord;
- if(counter == s.length() && counter < temp_s.length()) {
- newWord = new MultiNode(MAIN_PREFIX);
- newTempWord = new MultiNode(temp_word[counter]);
- this.allwords++;
- this.words++;
- }
- else if(counter == temp_s.length() && counter < s.length()) {
- newWord = new MultiNode(word[counter]);
- newTempWord = new MultiNode(MAIN_PREFIX);
- this.allwords++;
- this.words++;
- }
- else {
- newWord = new MultiNode(word[counter]);
- newTempWord = new MultiNode(temp_word[counter]);
- this.allwords++;
- this.words++;
- }
- newWord.setLeaf(s);
- newTempWord.setLeaf(temp_s);
- newTempWord.setWordcounter(temp_wordcounter);
- node.addNode(newWord);
- node.addNode(newTempWord);
- }
- }
- /**
- * Wie häufig kommt s vor?
- * @param s Wort
- * @return Häufigkeit Vorkommen
- */
- public int count(String s) {
- if(s == null || s.length() < 0 )
- return 0;
- if(s.equals(""))
- return emptystring;
- char word[] = s.toCharArray();
- int counter = 0;
- MultiNode node = root;
- while(counter < word.length - 1 && !node.isNodeListEmpty() && node.isNodeInList(word[counter])) {
- node = node.findNode(word[counter]);
- counter++;
- }
- if(node.getLeaf() != null && node.getLeaf().equals(s))
- return node.getWordcounter();
- if(node.isNodeInList(word[counter])) {
- node = node.findNode(word[counter]);
- if(node.getLeaf() != null && node.getLeaf().equals(s))
- return node.getWordcounter();
- if(node.isNodeInList(MAIN_PREFIX)) {
- node = node.findNode(MAIN_PREFIX);
- if(node.getLeaf() != null && node.getLeaf().equals(s))
- return node.getWordcounter();
- }
- }
- return 0;
- }
- /**
- * Entferne alle Vorkommen
- * @param s Wort
- * @return true gdw s mindestens einmal vorkam
- */
- public boolean remove(String s) {
- return false;
- }
- /**
- * Anzahl der Vorkommen aller Wörter
- * @return Anzahl alle Vorkommen
- */
- public int noOccurences() {
- return allwords;
- }
- /**
- * Anzahl der verschiedenen Wörter
- * @return Anzahl verschiedener Wörter
- */
- public int noWords() {
- return words;
- }
- /**
- * Iteriere über die vorkommenden Objekte
- * @return Iterator
- */
- public Iterator iterator() {
- return new Iterator() {
- private List<MultiNode> list = new LinkedList<MultiNode>();
- private Iterator it;
- private boolean buildIterator = false;
- private void buildIteratorArray() {
- buildIteratorArray(root);
- }
- private void buildIteratorArray(MultiNode node) {
- char keys[] = node.findKeys().toCharArray();
- for(int i = 0; i < keys.length; i++) {
- MultiNode t = node.findNode(keys[i]);
- if(t.getLeaf() != null) {
- list.add(t);
- }
- else
- buildIteratorArray(t);
- }
- }
- public boolean hasNext() {
- if(!buildIterator) {
- buildIteratorArray();
- it = list.iterator();
- buildIterator = true;
- }
- return it.hasNext();
- }
- public Object next() {
- MultiNode t = (MultiNode)it.next();
- return t.getLeaf();
- }
- public void remove() {
- // TODO Auto-generated method stub
- }
- };
- }
- }
Datei: WordCount.java
Quellcode
- package U8;
- import java.util.Map;
- import java.util.HashMap;
- import java.util.Iterator;
- import fhw.*;
- /**
- * @author Peter Barth
- * Testet die SearchList Implementierung
- * Einfach nur benutzen...
- */
- //--> geaenderte Version von sbern001
- public class WordCount {
- /**
- * @param args Dateinamen die zu verarbeiten sind
- */
- public static void main(String[] args) {
- String[] dateien =
- {
- "Woerter.txt",
- "AMidSummersNightDream.txt",
- "RomeoAndJuliet.txt",
- "words.txt"
- };
- if (args.length > 0)
- dateien = args;
- for (String datei : dateien) {
- test(datei, ADSTool.readStringArray("U8/" + datei));
- }
- }
- static String format = "%30s | %6s %6s | %10s | %10s | %10s | %10s\n";
- static String splitregex = "[ \t\n,:.]+";
- static boolean test(String name, String[] zeilen) {
- String anzahl, verschiedene, einfuegen, iterieren, zugriff, loeschen;
- int count = 0;
- SearchTrie sl = new SearchTrie(true); // Testet Ihre Implementierung
- Map hm = makeMap(zeilen); // Zum Gegentesten
- ADSTool.resetTime();
- for (int j = 0; j < zeilen.length; j++) {
- String[] woerter = zeilen[j].split(splitregex);
- for (int k = 0; k < woerter.length; k++) {
- // System.out.println(woerter[k]);
- sl.add(woerter[k]);
- count++;
- }
- }
- anzahl = Integer.toString(sl.noOccurences());
- verschiedene = Integer.toString(sl.noWords());
- sl.showTree(); // Zeigt die Struktur des Baums
- einfuegen = ADSTool.stringRTime();
- Iterator it = sl.iterator();
- count -= sl.getEmptyStrin();
- while (it.hasNext()) {
- String s = (String) it.next();
- int i = sl.count(s);
- count -= i;
- }
- iterieren = ADSTool.stringRTime();
- if (count != 0) {
- System.out.println("Fehler - Anzahl der Einträge " + count);
- return false;
- }
- it = hm.keySet().iterator();
- while (it.hasNext()) {
- String s = (String) it.next();
- int hmcount = ((Integer) hm.get(s)).intValue();
- if (hmcount != sl.count(s)) {
- System.err.println("Fehler - Anzahl der Vorkommen bei" + s);
- System.err.println(
- " Es sollten "
- + hmcount
- + " sein, sind aber "
- + sl.count(s));
- return false;
- }
- }
- zugriff = ADSTool.stringRTime();
- // it = hm.keySet().iterator();
- // while (it.hasNext()) {
- // String s = (String) it.next();
- // //.remove(
- // if (sl.count(s) != 0) {
- // System.err.println("Fehler - Element " + s + " nicht gelöscht");
- // return false;
- // }
- // }
- // if (sl.noOccurences() != 0 || sl.noWords() != 0) {
- // System.err.println("Fehler - Searchliste nicht leer");
- // return false;
- // }
- loeschen = ADSTool.stringRTime();
- System.out.format(format, "Name", "Worte", "Versch", "Einfügen", "Iterieren", "Zugriff", "Löschen");
- System.out.format(format, name, anzahl, verschiedene, einfuegen, iterieren, zugriff, loeschen);
- return true;
- }
- /**
- * Ein HashMap die dasselbe macht wie SearchList
- * wird nur zum Testen gemacht, kommt später noch
- * als Thema - nicht daran aufhalten...
- * @param zeilen Strings zum Hinzufügen
- * @return Map der Häufigkeiten
- */
- static Map<String, Integer> makeMap(String[] zeilen) {
- Map<String, Integer> hm = new HashMap<String, Integer>();
- for (int j = 0; j < zeilen.length; j++) {
- String[] woerter = zeilen[j].split(splitregex);
- for (int k = 0; k < woerter.length; k++) {
- if (hm.containsKey(woerter[k])) {
- int count = hm.get(woerter[k]);
- hm.put(woerter[k], count + 1);
- } else {
- hm.put(woerter[k], 1);
- }
- }
- }
- return hm;
- }
- }