2 people like it.
Like the snippet!

Similar string Markov chain

Generates strings that are similar to the input, as measured by the probability of a symbol depending on preceding symbols. (Markov chain) The order, which defines how many preceding symbols to look at before placing another, is variable.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45: 
46: 
47: 
48: 
49: 
50: 
51: 
52: 
53: 
54: 
55:

// Generates strings that are similar to the input, as measured by the
// probability of a character depending on the previous one. (Markov chain)

/// Reads a map of next characters' probabilities from a sample.
let readMap (s : string) =
    s |> Seq.windowed 3 |> Seq.groupBy (fun a -> sprintf "%c%c" a.[0] a.[1])
    |> Seq.map (fun (a, b) ->
        let counted = b |> Seq.map (fun arr -> arr.[2])
                        |> Seq.countBy id |> Seq.toList
        let total = List.sumBy snd counted
        a, counted |> List.map (fun (c, i) -> c, float i / float total))
    |> Map.ofSeq

// System.Random is broken. Replace it if you want reliable randomness.
let random = let r = System.Random() in fun () -> r.NextDouble()

/// Helper to get one character from a list of choices with probabilities
let getChar prev cases =
    let rec run r = function
        | [] -> failwith "getChar error"
        | (c, p) :: t when r > p -> run (r-p) t
        | (c, _) :: _ -> c
    run (random() * 0.999) cases // precision safety

/// Creates text according to a distribution. Fills in spaces if accumulator is empty.
let rec generate length acc map =
    if length < 1 then acc |> List.rev |> List.fold (sprintf "%s%c") "" else
    let acc' =
        match acc with
        | h2 :: h1 :: t when Map.containsKey (sprintf "%c%c" h1 h2) map ->
            let key = sprintf "%c%c" h1 h2
            getChar key (map.[key]) :: acc
        | _ -> ' ' :: acc
    generate (length - 1) acc' map

/// Generates words from sample. Handles space-separated words completely separately.
let wordwise length input =
    let out = (" " + input).Replace(" ", "  ")
              |> readMap |> generate length [' '; ' ']
    out.Replace("  ", " ").Remove(0,1) |> printfn "%s"


// Samples (input a long list of names to get more useful results):

"lololololol zomg roflmao"
|> wordwise 60

"Mercury Venus Earth Mars Asteroid Belt Jupiter Saturn Neptune Pluto Moon Terra Luna \
Adrastea Ganymede Callisto Europa Himalia Amalthea Thebe Elara Metis Pasiphae Carme \
Sinope Lysithea Ananke Leda Themisto Callirrhoe Praxidike Megaclite Locaste Taygete \
Kalyke Autonoe Harpalyke Titan Rhea Iapetus Dione Tethys Enceladus Mimas Hyperion \
Phoebe Janus Epimetheus Prometheus Pandora Titania Oberon Umbriel Ariel Miranda \
Sycorax Puck Portia Juliet Caliban Belinda Cressida Triton Proteus Nereid Larissa \
Galatea Despina Thalassa Charon"
|> wordwise 200

val readMap : s:string -> Map<string,(char * float) list>

Full name: Script.readMap

Reads a map of next characters' probabilities from a sample.

val s : string

Multiple items
val string : value:'T -> string

Full name: Microsoft.FSharp.Core.Operators.string

--------------------
type string = System.String

Full name: Microsoft.FSharp.Core.string

module Seq

from Microsoft.FSharp.Collections

val windowed : windowSize:int -> source:seq<'T> -> seq<'T []>

Full name: Microsoft.FSharp.Collections.Seq.windowed

val groupBy : projection:('T -> 'Key) -> source:seq<'T> -> seq<'Key * seq<'T>> (requires equality)

Full name: Microsoft.FSharp.Collections.Seq.groupBy

val a : char []

val sprintf : format:Printf.StringFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.sprintf

val map : mapping:('T -> 'U) -> source:seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.map

val a : string

val b : seq<char []>

val counted : (char * int) list

val arr : char []

val countBy : projection:('T -> 'Key) -> source:seq<'T> -> seq<'Key * int> (requires equality)

Full name: Microsoft.FSharp.Collections.Seq.countBy

val id : x:'T -> 'T

Full name: Microsoft.FSharp.Core.Operators.id

val toList : source:seq<'T> -> 'T list

Full name: Microsoft.FSharp.Collections.Seq.toList

val total : int

Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>

val sumBy : projection:('T -> 'U) -> list:'T list -> 'U (requires member ( + ) and member get_Zero)

Full name: Microsoft.FSharp.Collections.List.sumBy

val snd : tuple:('T1 * 'T2) -> 'T2

Full name: Microsoft.FSharp.Core.Operators.snd

val map : mapping:('T -> 'U) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.map

val c : char

val i : int

Multiple items
val float : value:'T -> float (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.float

--------------------
type float = System.Double

Full name: Microsoft.FSharp.Core.float

--------------------
type float<'Measure> = float

Full name: Microsoft.FSharp.Core.float<_>

Multiple items
module Map

from Microsoft.FSharp.Collections

--------------------
type Map<'Key,'Value (requires comparison)> =
  interface IEnumerable
  interface IComparable
  interface IEnumerable<KeyValuePair<'Key,'Value>>
  interface ICollection<KeyValuePair<'Key,'Value>>
  interface IDictionary<'Key,'Value>
  new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>
  member Add : key:'Key * value:'Value -> Map<'Key,'Value>
  member ContainsKey : key:'Key -> bool
  override Equals : obj -> bool
  member Remove : key:'Key -> Map<'Key,'Value>
  ...

Full name: Microsoft.FSharp.Collections.Map<_,_>

--------------------
new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>

val ofSeq : elements:seq<'Key * 'T> -> Map<'Key,'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Map.ofSeq

val random : (unit -> float)

Full name: Script.random

val r : System.Random

namespace System

Multiple items
type Random =
  new : unit -> Random + 1 overload
  member Next : unit -> int + 2 overloads
  member NextBytes : buffer:byte[] -> unit
  member NextDouble : unit -> float

Full name: System.Random

--------------------
System.Random() : unit
System.Random(Seed: int) : unit

System.Random.NextDouble() : float

val getChar : prev:'a -> cases:('b * float) list -> 'b

Full name: Script.getChar

Helper to get one character from a list of choices with probabilities

val prev : 'a

val cases : ('b * float) list

val run : (float -> ('c * float) list -> 'c)

val r : float

val failwith : message:string -> 'T

Full name: Microsoft.FSharp.Core.Operators.failwith

val c : 'c

val p : float

val t : ('c * float) list

val generate : length:int -> acc:char list -> map:Map<string,(char * float) list> -> string

Full name: Script.generate

Creates text according to a distribution. Fills in spaces if accumulator is empty.

val length : int

val acc : char list

val map : Map<string,(char * float) list>

val rev : list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.rev

val fold : folder:('State -> 'T -> 'State) -> state:'State -> list:'T list -> 'State

Full name: Microsoft.FSharp.Collections.List.fold

val acc' : char list

val h2 : char

val h1 : char

val t : char list

val containsKey : key:'Key -> table:Map<'Key,'T> -> bool (requires comparison)

Full name: Microsoft.FSharp.Collections.Map.containsKey

val key : string

val wordwise : length:int -> input:string -> unit

Full name: Script.wordwise

Generates words from sample. Handles space-separated words completely separately.

val input : string

val out : string

System.String.Replace(oldValue: string, newValue: string) : string
System.String.Replace(oldChar: char, newChar: char) : string

val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn

Previous Version Raw view Test code New version

More information

Link:	http://fssnip.net/ol
Posted:	3 years ago
Author:	Vandroiy
Tags:	random , generator , markov chain