-
Notifications
You must be signed in to change notification settings - Fork 1
/
HierachNGram.cs
123 lines (107 loc) · 4.18 KB
/
HierachNGram.cs
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
/* Copyright (c) 2018-2024 Nuno Fachada and contributors
* Distributed under the MIT License (See accompanying file LICENSE or copy
* at http://opensource.org/licenses/MIT) */
using System.Collections.Generic;
using LibGameAI.Util;
namespace LibGameAI.NGrams
{
/// <summary>
/// Hierarchical N-Gram.
/// </summary>
/// <typeparam name="T">The type of the actions.</typeparam>
public class HierarchNGram<T> : INGram<T>
{
// Threshold: minimum frequency for sequence of actions to be considered
private readonly int threshold;
// Array of N-Grams
private readonly NGram<T>[] predictors;
/// <inheritdoc/>
public int NValue { get; }
/// <summary>
/// Creates a new hierarchical N-Gram.
/// </summary>
/// <param name="nValue">The N in N-Gram (window size + 1).</param>
/// <param name="threshold">
/// Minimum number of observations for a specific N-Gram to return a
/// prediction.
/// </param>
public HierarchNGram(int nValue, int threshold)
{
// Keep the N value
NValue = nValue;
// Keep the threshold
this.threshold = threshold;
// Instantiate the array of N-Grams
predictors = new NGram<T>[nValue];
// Instantiate the individual N-Grams
for (int i = 0; i < nValue; i++)
predictors[i] = new NGram<T>(i + 1);
}
/// <summary>
/// Register a sequence of actions.
/// </summary>
/// <param name="actions">
/// The actions list, which should be at least of size 1.
/// </param>
public void RegisterSequence(IReadOnlyList<T> actions)
{
// Register the sequence of actions in each Ni-Gram
for (int i = 0; i < NValue; i++)
{
// Are there enough actions for the current Ni-Gram?
if (actions.Count >= i + 1)
{
ReadOnlyListSegment<T> subactions =
new ReadOnlyListSegment<T>(
actions,
actions.Count - i - 1,
i + 1);
// Register the sequence of actions in the current Ni-Gram
predictors[i].RegisterSequence(subactions);
}
}
}
/// <summary>
/// Get the most likely action given a sequence of actions.
/// </summary>
/// <param name="actions">
/// The actions list, which should be at least of size 1.
/// </param>
/// <returns>
/// The most likely action for the given a sequence of actions.
/// </returns>
public T GetMostLikely(IReadOnlyList<T> actions)
{
// Declare variable for best action and set it to its default value
T bestAction = default;
// Go through the various Ni-Grams
for (int i = 0; i < NValue; i++)
{
// Are there enough actions for the current Ni-Gram?
if (actions.Count >= NValue - i - 1)
{
// Get current Ni-Gram
NGram<T> p = predictors[NValue - i - 1];
// Create a view containing only the actions for the
// current Ni-Gram
ReadOnlyListSegment<T> subactions =
new ReadOnlyListSegment<T>(
actions,
actions.Count + i + 1 - NValue,
NValue - i - 1);
// Get frequency of action sequence in the current Ni-Gram
int numActions = p.GetActionsFrequency(subactions);
// Is that frequency larger than the threshold?
if (numActions > threshold)
{
// Then use this action
bestAction = p.GetMostLikely(subactions);
break;
}
}
}
// Return the best action
return bestAction;
}
}
}