Skip to content

Instantly share code, notes, and snippets.

@aNNiMON
Last active August 29, 2015 13:58
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save aNNiMON/10003677 to your computer and use it in GitHub Desktop.
Save aNNiMON/10003677 to your computer and use it in GitHub Desktop.
Алгоритм Маркова
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");
}
}
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);
}
}
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;
}
}
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