Last active
August 29, 2015 13:58
-
-
Save aNNiMON/10003677 to your computer and use it in GitHub Desktop.
Алгоритм Маркова
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package algorithmmarkov; | |
import java.util.ArrayList; | |
public class AlgorithmMarkov { | |
public static void main(String[] args) { | |
Rules rules4to2 = Rules.create() | |
.add("~0", "00~") | |
.add("~1", "01~") | |
.add("~2", "10~") | |
.add("~3", "11~") | |
.add("~", "", true) // заключительная подстановка | |
.add("", "~"); | |
Rules rules16to2 = Rules.create() | |
.add("~0", "0000~") | |
.add("~1", "0001~") | |
.add("~2", "0010~") | |
.add("~3", "0011~") | |
.add("~4", "0100~") | |
.add("~5", "0101~") | |
.add("~6", "0110~") | |
.add("~7", "0111~") | |
.add("~8", "1000~") | |
.add("~9", "1001~") | |
.add("~A", "1010~") | |
.add("~B", "1011~") | |
.add("~C", "1100~") | |
.add("~D", "1101~") | |
.add("~E", "1110~") | |
.add("~F", "1111~") | |
.add("~", "", true) // заключительная подстановка | |
.add("", "~"); | |
Markov.create() | |
.rules(rules4to2) | |
.process("213022") | |
.process("1323121321") | |
.rules(rules16to2) | |
.process("7F") | |
.process("CAFEBABE"); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com.annimon.algorithmmarkov; | |
import java.io.PrintStream; | |
/** | |
* Алгоритм Маркова. | |
* @author aNNiMON | |
*/ | |
public final class Markov { | |
public static Markov create() { | |
return new Markov(); | |
} | |
public static Markov with(Rules rules) { | |
final Markov markov = new Markov(); | |
markov.rules(rules); | |
return markov; | |
} | |
private PrintStream printStream; | |
private Rules rules; | |
private int iterateLimit; | |
private Markov() { | |
iterateLimit = 1000; | |
printStream = System.out; | |
} | |
public Markov rules(Rules rules) { | |
this.rules = rules; | |
return this; | |
} | |
public Markov iterateLimit(int iterateLimit) { | |
this.iterateLimit = iterateLimit; | |
return this; | |
} | |
public Markov printStream(PrintStream printStream) { | |
this.printStream = printStream; | |
return this; | |
} | |
public Markov process(String word) { | |
if (rules == null) throw new IllegalArgumentException("Rules is empty"); | |
int step = 0; | |
boolean iterate = true; | |
while(iterate && (step < iterateLimit)) { | |
final String prev = word; | |
for (Object rule : rules) { | |
Replacement current = (Replacement) rule; | |
String replaceString = replaceFirst(word, current); | |
if (!replaceString.equals(word)) { | |
word = replaceString; | |
step++; | |
// Если произошла заключительная подстановка - выходим | |
if (current.endless) iterate = false; | |
break; | |
} | |
} | |
if (prev.equals(word)) break; | |
printStream.println(step + " P=\"" + word + "\""); | |
} | |
return this; | |
} | |
private static String replaceFirst(String str, Replacement replace) { | |
if (replace.from.length() == 0) return replace.to + str;// _ -> * | |
return str.replaceFirst(replace.from, replace.to); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com.annimon.algorithmmarkov; | |
/** | |
* Подстановка. | |
* @author aNNiMON | |
*/ | |
class Replacement { | |
/** Заменяемые строки. */ | |
final String from, to; | |
/** Заключительная подстановка. */ | |
final boolean endless; | |
Replacement(String from, String to, boolean endless) { | |
this.from = from; | |
this.to = to; | |
this.endless = endless; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com.annimon.algorithmmarkov; | |
import java.util.ArrayList; | |
import java.util.Iterator; | |
import java.util.List; | |
/** | |
* Правила подстановки. | |
* @author aNNiMON | |
*/ | |
public final class Rules implements Iterable { | |
private final List<Replacement> rules; | |
public static Rules create() { | |
return new Rules(); | |
} | |
private Rules() { | |
rules = new ArrayList<>(); | |
} | |
public Rules add(String from, String to) { | |
return add(from, to, false); | |
} | |
public Rules add(String from, String to, boolean endless) { | |
rules.add(new Replacement(from, to, endless)); | |
return this; | |
} | |
@Override | |
public Iterator iterator() { | |
return rules.iterator(); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment