Code:
/ Dotnetfx_Win7_3.5.1 / Dotnetfx_Win7_3.5.1 / 3.5.1 / WIN_WINDOWS / lh_tools_devdiv_wpf / Windows / wcp / Speech / Src / Internal / SrgsCompiler / graph.cs / 1 / graph.cs
//------------------------------------------------------------------
//
// Copyright (c) Microsoft Corporation. All rights reserved.
//
//
// Description:
// CFG Grammar backend
//
// History:
// 5/1/2004 jeanfp Created from the Sapi Managed code
//-----------------------------------------------------------------
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Diagnostics;
using System.Globalization;
using System.Runtime.InteropServices;
using System.Text;
using System.IO;
using System.Speech.Internal.SrgsParser;
namespace System.Speech.Internal.SrgsCompiler
{
// Doubled chained linked list for fast removal of states.
// Checks are made to ensure that the State pointers are never reused.
#if DEBUG
[DebuggerDisplay ("Count = {Count}")]
[DebuggerTypeProxy (typeof (GraphDebugDisplay))]
#endif
internal class Graph : IEnumerable
{
//*******************************************************************
//
// Internal Methods
//
//*******************************************************************
#region Internal Methods
internal void Add (State state)
{
state.Init ();
if (_startState == null)
{
_curState = _startState = state;
}
else
{
_curState = _curState.Add (state);
}
}
internal void Remove (State state)
{
if (state == _startState)
{
_startState = state.Next;
}
if (state == _curState)
{
_curState = state.Prev;
}
state.Remove ();
}
IEnumerator IEnumerable.GetEnumerator ()
{
for (State item = _startState; item != null; item = item.Next)
{
yield return item;
}
}
IEnumerator IEnumerable.GetEnumerator ()
{
for (State item = _startState; item != null; item = item.Next)
{
yield return item;
}
}
///
/// Creates a new state handle in a given rule
///
///
///
/// Deletet a state
///
///
///
/// Optimizes the grammar network by removing the epsilon states and merging
/// duplicate transitions. See GrammarOptimization.doc for details.
///
internal void Optimize ()
{
foreach (State state in this)
{
NormalizeTransitionWeights (state);
}
#if DEBUG
// Remove redundant epsilon transitions.
int cStates = Count;
RemoveEpsilonStates ();
if (Count != cStates)
{
System.Diagnostics.Trace.WriteLine ("Grammar compiler, additional Epsilons could have been removed :" + (cStates - Count).ToString ());
//System.Diagnostics.Debug.Assert (_states.Count == cStates);
}
// Remove duplicate transitions.
#endif
MergeDuplicateTransitions ();
#if DEBUG
// Remove redundant epsilon transitions again now that identical epsilon transitions have been removed.
//DumpGrammarStatistics("GrammarOptimization: DuplicateRemoval");
cStates = Count;
RemoveEpsilonStates ();
//System.Diagnostics.Debug.Assert (_states.Count == cStates);
if (Count != cStates)
{
System.Diagnostics.Trace.WriteLine ("Grammar compiler, additional Epsilons could have been removed post merge transition :" + (cStates - Count).ToString ());
}
// Verify the transition weights are normalized.
//DumpGrammarStatistics ("GrammarOptimization: Final");
foreach (State state in this)
{
double flSumWeights = 0.0f; // Compute the sum of the weights.
int cArcs = 0;
foreach (Arc arc in state.OutArcs)
{
flSumWeights += arc.Weight;
cArcs++;
}
float maxWeightError = 0.00001f * cArcs;
if (flSumWeights != 0.0f && maxWeightError - Math.Abs (flSumWeights - 1.0f) < 0)
{
System.Diagnostics.Debug.Assert (true);
}
}
#endif
}
///
/// Description:
/// Change all transitions ending at SourceState to end at DestState, instead.
/// Replace references to SourceState with references to DestState before deleting SourceState.
/// - There may be additional duplicate input transitions at DestState after the move.
///
/// Assumptions:
/// - SourceState == !null, RuleInitialState, !DestState, ...
/// - DestState == null, RuleInitialState, !SourceState, ...
/// - SourceState.OutputArc.IsEmpty
/// - !(SourceState == RuleInitialState AND DestState == nul)
///
/// Algorithm:
/// - For each input transition into SourceState
/// - Transition.EndState = DestState
/// - If DestState != null, DestState.InputArcs += Transition
/// - SourceState.InputArcs -= Transition
/// - SourceState.InputArcs.Clear()
/// - If SourceState == RuleInitialState, RuleInitialState = DestState
/// - Delete SourceState
///
///
///
internal void MoveInputTransitionsAndDeleteState (State srcState, State destState)
{
System.Diagnostics.Debug.Assert (srcState != null);
System.Diagnostics.Debug.Assert (srcState != destState);
// For each input transition into SourceState, change EndState to DestState.
List arcs = srcState.InArcs.ToList ();
foreach (Arc arc in arcs)
{
// Change EndState to DestState
arc.End = destState;
}
//srcState.InArcs.RemoveRange (0,srcState.InArcs.Count);
// Replace references to SourceState with references to DestState before deleting SourceState
if (srcState.Rule._firstState == srcState) // Update RuleInitialState reference, if necessary
{
System.Diagnostics.Debug.Assert (destState != null);
srcState.Rule._firstState = destState;
}
// Delete SourceState
System.Diagnostics.Debug.Assert (srcState != null);
//System.Diagnostics.Debug.Assert (srcState.InArcs.IsEmpty);
System.Diagnostics.Debug.Assert (srcState.OutArcs.IsEmpty);
DeleteState (srcState); // Delete state from handle table
}
///
/// Description:
/// Change all transitions starting at SourceState to start at DestState, instead.
/// Deleting SourceState.
/// - The weights on the transitions have been properly adjusted.
/// The weights are not changed when moving transitions.
/// - There may be additional duplicate input transitions at DestState after the move.
///
/// Assumptions:
/// - SourceState == !null, !RuleInitialState, !DestState, ...
/// - DestState == !null, RuleInitialState, !SourceState, ...
/// - SourceState.InputArc.IsEmpty
///
/// Algorithm:
/// - For each output transition from SourceState
/// - Transition.StartState = DestState
/// - DestState.OutputArcs += Transition
/// - Delete SourceState
///
///
///
internal void MoveOutputTransitionsAndDeleteState (State srcState, State destState)
{
System.Diagnostics.Debug.Assert (srcState != null);
System.Diagnostics.Debug.Assert ((destState != null) && (destState != srcState));
System.Diagnostics.Debug.Assert (srcState.InArcs.IsEmpty);
// For each output transition from SourceState, change StartState to DestState.
List arcs = srcState.OutArcs.ToList ();
foreach (Arc arc in arcs)
{
// Change StartState to DestState
arc.Start = destState;
}
// Delete SourceState
System.Diagnostics.Debug.Assert (srcState != null);
System.Diagnostics.Debug.Assert (srcState.InArcs.IsEmpty);
//System.Diagnostics.Debug.Assert (srcState.OutArcs.IsEmpty);
DeleteState (srcState); // Delete state from handle table
}
#endregion
//********************************************************************
//
// Internal Property
//
//*******************************************************************
#region Internal Property
#if DEBUG
internal State First
{
get
{
return _startState;
}
}
internal int Count
{
get
{
int c = 0;
for (State se = _startState; se != null; se = se.Next)
{
c++;
}
return c;
}
}
#endif
#endregion
//********************************************************************
//
// Private Methods
//
//********************************************************************
#region Private Methods
#if DEBUG
///
/// Description:
/// Removing epsilon states from the grammar network.
/// See GrammarOptimization.doc for details.
/// - There may be additional duplicate transitions after removing epsilon transitions.
///
/// Algorithm:
/// - For each State in the graph,
/// - If the state has a single input epsilon transition and is not the rule initial state,
/// - Move properties to the right, if necessary.
/// - If EpsilonTransition does not have properties and is not referenced by other properties,
/// - Delete EpsilonTransition.
/// - Multiply weight of all transitions from State by EpsilonTransition.Weight.
/// - MoveOutputTransitionsAndDeleteState(State, EpsilonTransition.StartState)
/// - If the state has a single output epsilon transition,
/// - Move properties to the left, if necessary.
/// - If EpsilonTransition does not have properties and is not referenced by other properties,
/// - Delete EpsilonTransition.
/// - MoveInputTransitionsAndDeleteState(State, EpsilonTransition.EndState)
///
/// Moving SemanticTag:
/// - InputEpsilonTransitions can move its semantic tag ownerships/references to the right.
/// - OutputEpsilonTransitions can move its semantic tag ownerships/references to the left.
///
private void RemoveEpsilonStates ()
{
// For each state in the grammar graph, remove excess input/output epsilon transitions.
for (State state = First, nextState = null; state != null; state = nextState)
{
nextState = state.Next;
if (state.InArcs.CountIsOne && state.InArcs.First.IsEpsilonTransition && (state != state.Rule._firstState))
{
// State has a single input epsilon transition and is not the rule initial state.
Arc epsilonArc = state.InArcs.First;
// Attempt to move properties referencing EpsilonArc to the right.
// Optimization can only be applied when the epsilon arc is not referenced by any properties.
if (MoveSemanticTagRight (epsilonArc))
{
// Delete the input epsilon transition
State pEpsilonStartState = epsilonArc.Start;
float flEpsilonWeight = epsilonArc.Weight;
DeleteTransition (epsilonArc);
// Multiply weight of all transitions from state by EpsilonWeight.
foreach (Arc arc in state.OutArcs)
{
arc.Weight *= flEpsilonWeight;
}
// Move all output transitions from state to pEpsilonStartState and delete state if appropriate.
if (state != pEpsilonStartState)
{
MoveOutputTransitionsAndDeleteState (state, pEpsilonStartState);
}
}
}
// Optimize output epsilon transition, if possible
else if ((state.OutArcs.CountIsOne) && state.OutArcs.First.IsEpsilonTransition && (state != state.Rule._firstState))
{
// State has a single output epsilon transition
Arc epsilonArc = state.OutArcs.First;
// Attempt to move properties referencing EpsilonArc to the left.
// Optimization can only be applied when the epsilon arc is not referenced by any properties
// and when the arc does not connect RuleInitialState to null.
if (!((state == state.Rule._firstState) && (epsilonArc.End == null)) && MoveSemanticTagLeft (epsilonArc))
{
// Delete the output epsilon transition
State pEpsilonEndState = epsilonArc.End;
DeleteTransition (epsilonArc);
// Move all input transitions from state to pEpsilonEndState and delete state if appropriate.
if (state != pEpsilonEndState)
{
MoveInputTransitionsAndDeleteState (state, pEpsilonEndState);
}
}
}
}
}
#endif
///
/// Description:
/// Remove duplicate transitions starting from the same state, or ending at the same state.
/// See GrammarOptimization.doc for details.
///
/// Algorithm:
/// - Add all states to ToDoList
/// - For each state left in the ToDoList,
/// - Merge any duplicate output transitions.
/// - Add all states to ToDoList in reverse order.
/// - Remove duplicate transitions to null (special case since there is no state for FinalState)
/// - For each state left in the ToDoList,
/// - Merge any duplicate input transitions.
///
/// Notes:
/// - For best optimization, we need to move semantic properties referencing the transitions.
///
private void MergeDuplicateTransitions ()
{
List tempList = new List ();
// Build collection of states with potential identical transition.
foreach (State state in this)
{
if (state.OutArcs.ContainsMoreThanOneItem)
{
// Merge identical transitions in arcs
MergeIdenticalTransitions (state.OutArcs, tempList);
}
}
// Collection of states with potential transitions to merge
Stack mergeStates = new Stack ();
RecursiveMergeDuplicatedOutputTransition (mergeStates);
RecursiveMergeDuplicatedInputTransition (mergeStates);
}
private void RecursiveMergeDuplicatedInputTransition (Stack mergeStates)
{
// Build collection of states with potential duplicate input transitions to merge.
foreach (State state in this)
{
if (state.InArcs.ContainsMoreThanOneItem)
{
MergeDuplicateInputTransitions (state.InArcs, mergeStates);
}
}
// For each state in the collection, merge any duplicate input transitions.
List tempList = new List ();
while (mergeStates.Count > 0)
{
State state = mergeStates.Pop ();
if (state.InArcs.ContainsMoreThanOneItem)
{
// Merge identical transitions in arcs that may have been created
MergeIdenticalTransitions (state.InArcs, tempList);
MergeDuplicateInputTransitions (state.InArcs, mergeStates);
}
}
}
private void RecursiveMergeDuplicatedOutputTransition (Stack mergeStates)
{
// Build collection of states with potential duplicate output transitions to merge.
foreach (State state in this)
{
if (state.OutArcs.ContainsMoreThanOneItem)
{
MergeDuplicateOutputTransitions (state.OutArcs, mergeStates);
}
}
// For each state in the collection, merge any duplicate output transitions.
List tempList = new List ();
while (mergeStates.Count > 0)
{
State state = mergeStates.Pop ();
if (state.OutArcs.ContainsMoreThanOneItem)
{
// Merge identical transitions in arcs that may have been created
MergeIdenticalTransitions (state.OutArcs, tempList);
MergeDuplicateOutputTransitions (state.OutArcs, mergeStates);
}
}
}
///
/// Description:
/// Sort and iterate through the input arcs and remove duplicate input transitions.
/// See GrammarOptimization.doc for details.
///
/// Algorithm:
/// - MergeIdenticalTransitions(Arcs)
/// - Sort the input transitions from the state (by content and # output arcs from start state)
/// - For each set of transitions with identical content and StartState.OutputArcs.Count() == 1
/// - Move semantic properties to the left, if necessary.
/// - Label the first property-less transition as CommonArc
/// - For each successive property-less transition (DuplicateArc)
/// - Delete DuplicateArc
/// - MoveInputTransitionsAndDeleteState(DuplicateArc.StartState, CommonArc.StartState)
/// - Add CommonArc.StartState to ToDoList if not there already.
///
/// Moving SemanticTag:
/// - Duplicate input transitions can move its semantic tag ownerships/references to the left.
///
/// Collection of input transitions to collapse
/// Collection of states with potential transitions to merge
private void MergeDuplicateInputTransitions (ArcList arcs, Stack mergeStates)
{
List arcsToMerge = null;
// Reference Arc
Arc refArc = null;
bool refSet = false;
// Build a list of possible arcs to Merge
foreach (Arc arc in arcs)
{
// Skip transitions whose end state has other incoming transitions or if the end state has more than one incoming transition
bool skipTransition = arc.Start == null || !arc.Start.OutArcs.CountIsOne;
// Find next set of duplicate output transitions (potentially with properties).
if (refArc != null && Arc.CompareContent (arc, refArc) == 0)
{
if (!skipTransition)
{
// Lazy init as entering this loop is a rare event
if (arcsToMerge == null)
{
arcsToMerge = new List ();
}
// Add the first element
if (!refSet)
{
arcsToMerge.Add (refArc);
refSet = true;
}
arcsToMerge.Add (arc);
}
}
else
{
// New word, reset everything
refArc = skipTransition ? null : arc;
refSet = false;
}
}
// Combine the arcs if possible
if (arcsToMerge != null)
{
// Sort the arc per content and output transition
arcsToMerge.Sort (Arc.CompareForDuplicateInputTransitions);
refArc = null;
Arc commonArc = null; // Common property-less transition to merge into
State commonStartState = null;
bool fCommonStartStateChanged = false; // Did CommonStartState change and need re-optimization?
foreach (Arc arc in arcsToMerge)
{
if (refArc == null || Arc.CompareContent (arc, refArc) != 0)
{
// Purge the last operations and reset all the local
refArc = arc;
// If CommonStartState changed, renormalize weights and add it to MergeStates for reoptimization.
if (fCommonStartStateChanged)
{
AddToMergeStateList (mergeStates, commonStartState);
}
// Reset the arcs
commonArc = null;
commonStartState = null;
fCommonStartStateChanged = false;
}
// For each property-less duplicate transition
Arc duplicatedArc = arc;
State duplicatedStartState = duplicatedArc.Start;
// Attempt to move properties referencing duplicate arc to the right.
// Optimization can only be applied when the duplicate arc is not referenced by any properties
// and the duplicate end state is not the RuleOutitalState.
if (MoveSemanticTagLeft (duplicatedArc))
{
// duplicatedArc != commonArc
if (commonArc != null)
{
if (!fCommonStartStateChanged)
{
// Processing first duplicate arc.
// Multiply the weights of transitions from CommonStartState by CommonArc.Weight.
foreach (Arc arcOut in commonStartState.OutArcs)
{
arcOut.Weight *= commonArc.Weight;
}
fCommonStartStateChanged = true; // Output transitions of CommonStartState changed.
}
// Multiply the weights of transitions from DuplicateStartState by DuplicateArc.Weight.
foreach (Arc arcOut in duplicatedStartState.OutArcs)
{
arcOut.Weight *= duplicatedArc.Weight;
}
duplicatedArc.Weight += commonArc.Weight;// Merge duplicate arc weight with common arc
Arc.CopyTags (commonArc, duplicatedArc, Direction.Left);
DeleteTransition (commonArc); // Delete successive duplicate transitions
// Move outputs of duplicate state to common state; Delete duplicate state
MoveInputTransitionsAndDeleteState (commonStartState, duplicatedStartState);
}
// Label first property-less transition as CommonArc
commonArc = duplicatedArc;
commonStartState = duplicatedStartState;
}
}
// If CommonStartState changed, renormalize weights and add it to MergeStates for reoptimization.
if (fCommonStartStateChanged)
{
AddToMergeStateList (mergeStates, commonStartState);
}
}
}
///
/// Description:
/// Sort and iterate through the output arcs and remove duplicate output transitions.
/// See GrammarOptimization.doc for details.
///
/// Algorithm:
/// - MergeIdenticalTransitions(Arcs)
/// - Sort the output transitions from the state (by content and # input arcs from end state)
/// - For each set of transitions with identical content, EndState != null, and EndState.InputArcs.Count() == 1
/// - Move semantic properties to the right, if necessary.
/// - Label the first property-less transition as CommonArc
/// - For each property-less transition (DuplicateArc) including CommonArc
/// - Multiply the weights of output transitions from DuplicateArc.EndState by DuplicateArc.Weight.
/// - If DuplicateArc != CommonArc
/// - CommonArc.Weight += DuplicateArc.Weight
/// - Delete DuplicateArc
/// - MoveOutputTransitionsAndDeleteState(DuplicateArc.EndState, CommonArc.EndState)
/// - Normalize weights of output transitions from CommonArc.EndState.
/// - Add CommonArc.EndtState to ToDoList if not there already.
///
/// Moving SemanticTag:
/// - Duplicate output transitions can move its semantic tag ownerships/references to the right.
///
/// Collection of output transitions to collapse
/// Collection of states with potential transitions to merge
private void MergeDuplicateOutputTransitions (ArcList arcs, Stack mergeStates)
{
List arcsToMerge = null;
// Reference Arc
Arc refArc = null;
bool refSet = false;
// Build a list of possible arcs to Merge
foreach (Arc arc in arcs)
{
// Skip transitions whose end state has other incoming transitions or if the end state has more than one incoming transition
bool skipTransition = arc.End == null || !arc.End.InArcs.CountIsOne;
// Find next set of duplicate output transitions (potentially with properties).
if (refArc != null && Arc.CompareContent (arc, refArc) == 0)
{
if (!skipTransition)
{
// Lazy init as entering this loop is a rare event
if (arcsToMerge == null)
{
arcsToMerge = new List ();
}
// Add the first element
if (!refSet)
{
arcsToMerge.Add (refArc);
refSet = true;
}
arcsToMerge.Add (arc);
}
}
else
{
// New word, reset everything
refArc = skipTransition ? null : arc;
refSet = false;
}
}
// Combine the arcs if possible
if (arcsToMerge != null)
{
// Sort the arc per content and output transition
arcsToMerge.Sort (Arc.CompareForDuplicateOutputTransitions);
refArc = null;
Arc commonArc = null; // Common property-less transition to merge into
State commonEndState = null;
bool fCommonEndStateChanged = false; // Did CommonEndState change and need re-optimization?
foreach (Arc arc in arcsToMerge)
{
if (refArc == null || Arc.CompareContent (arc, refArc) != 0)
{
// Purge the last operations and reset all the local
refArc = arc;
// If CommonEndState changed, renormalize weights and add it to MergeStates for reoptimization.
if (fCommonEndStateChanged)
{
AddToMergeStateList (mergeStates, commonEndState);
}
// Reset the arcs
commonArc = null;
commonEndState = null;
fCommonEndStateChanged = false;
}
// For each property-less duplicate transition
Arc duplicatedArc = arc;
State duplicatedEndState = duplicatedArc.End;
// Attempt to move properties referencing duplicate arc to the right.
// Optimization can only be applied when the duplicate arc is not referenced by any properties
// and the duplicate end state is not the RuleInitalState.
if ((duplicatedEndState != duplicatedEndState.Rule._firstState) && MoveSemanticTagRight (duplicatedArc))
{
// duplicatedArc != commonArc
if (commonArc != null)
{
if (!fCommonEndStateChanged)
{
// Processing first duplicate arc.
// Multiply the weights of transitions from CommonEndState by CommonArc.Weight.
foreach (Arc arcOut in commonEndState.OutArcs)
{
arcOut.Weight *= commonArc.Weight;
}
fCommonEndStateChanged = true; // Output transitions of CommonEndState changed.
}
// Multiply the weights of transitions from DuplicateEndState by DuplicateArc.Weight.
foreach (Arc arcOut in duplicatedEndState.OutArcs)
{
arcOut.Weight *= duplicatedArc.Weight;
}
duplicatedArc.Weight += commonArc.Weight;// Merge duplicate arc weight with common arc
Arc.CopyTags (commonArc, duplicatedArc, Direction.Right);
DeleteTransition (commonArc); // Delete successive duplicate transitions
// Move outputs of duplicate state to common state; Delete duplicate state
MoveOutputTransitionsAndDeleteState (commonEndState, duplicatedEndState);
}
// Label first property-less transition as CommonArc
commonArc = duplicatedArc;
commonEndState = duplicatedEndState;
}
}
// If CommonEndState changed, renormalize weights and add it to MergeStates for reoptimization.
if (fCommonEndStateChanged)
{
AddToMergeStateList (mergeStates, commonEndState);
}
}
}
private static void AddToMergeStateList (Stack mergeStates, State commonEndState)
{
NormalizeTransitionWeights (commonEndState);
if (!mergeStates.Contains (commonEndState))
{
mergeStates.Push (commonEndState);
}
}
///
/// Move any semantic tag ownership and optionally references to a unique
/// previous arc, if possible.
///
/// MoveReferences = true: Return if arc is propertyless after the move.
/// MoveReferences = false: Return if arc does not own semantic tag after the move.
/// The arc can still be referenced by other semantic tags.
///
///
///
/// Move any semantic tag ownership and optionally references to a unique
/// next arc, if possible.
///
/// MoveReferences = true: Return if arc is propertyless after the move.
/// MoveReferences = false: Return if arc does not own semantic tag after the move.
/// The arc can still be referenced by other semantic tags.
///
/// Force semantic tag references to always move with tag. See 37583.
/// This changes the range of words spanned by the tag, which is a bug for SAPI grammars.
///
///
///
/// Check if tags can be moved from a source arc to a destination
/// - Semantic interpretation. Tags cannot be moved if they would end up over a rule ref.
/// - Sapi properties. Tag can be put anywhere.
///
///
///
///
/// Description:
/// Detach and delete the specified transition from the graph.
/// Relocate or delete referencing semantic tags before deleting the transition.
///
/// Special Case:
/// Arc.EndState == null
/// Arc.Optional == true
///
///
private static void DeleteTransition (Arc arc)
{
// Arc cannot own SemanticTag
System.Diagnostics.Debug.Assert (arc.SemanticTagCount == 0);
// Arc cannot be referenced by SemanticTags
System.Diagnostics.Debug.Assert (arc.IsPropertylessTransition);
// Detach arc from start and end state
arc.Start = arc.End = null;
}
///
/// Description:
/// Merge identical transitions with identical content, StartState, and EndState.
///
///
///
///
private static void MergeIdenticalTransitions (ArcList arcs, List identicalWords)
{
// Need at least two transitions to merge.
System.Diagnostics.Debug.Assert (arcs.ContainsMoreThanOneItem);
// Need at least two transitions to merge.
List> segmentsToDelete = null;
Arc refArc = arcs.First;
// Accumulate a set of transition to delete
foreach (Arc arc in arcs)
{
if (Arc.CompareContent (refArc, arc) != 0)
{
// Identical transition
if (identicalWords.Count >= 2)
{
identicalWords.Sort (Arc.CompareIdenticalTransitions);
if (segmentsToDelete == null)
{
segmentsToDelete = new List> ();
}
// Add the list of same words into a list for further processing.
// The expectation of having an identical transition is very low so the code
// may be a bit slow.
segmentsToDelete.Add (new List (identicalWords));
}
identicalWords.Clear ();
}
refArc = arc;
identicalWords.Add (arc);
}
// Did the last word was replicated several times?
if (identicalWords.Count >= 2)
{
MergeIdenticalTransitions (identicalWords);
}
identicalWords.Clear ();
// Process the accumulated words
if (segmentsToDelete != null)
{
foreach (List segmentToDelete in segmentsToDelete)
{
MergeIdenticalTransitions (segmentToDelete);
}
}
}
///
/// Description:
/// Merge identical transitions with identical content, StartState, and EndState.
///
/// Algorithm:
/// - LastArc = Arcs[0]
/// - For each Arc in Arcs[1-],
/// - If Arc is identical to LastArc,
/// - LastArc.Weight += Arc.Weight
/// - Delete Arc
/// - Else LastArc = Arc
///
/// Moving SemanticTag:
/// - Identical transitions have identical semantic tags. Currently impossible to have identical
/// non-null tags.
/// - MoveSemanticTagReferences(DuplicateArc, CommonArc)
///
///
private static void MergeIdenticalTransitions (List identicalWords)
{
Collection arcsToDelete = null;
Arc refArc = null;
foreach (Arc arc in identicalWords)
{
if (refArc != null && Arc.CompareIdenticalTransitions (refArc, arc) == 0)
{
// Identical transition
arc.Weight += refArc.Weight;
refArc.ClearTags ();
if (arcsToDelete == null)
{
// delay the creation of the collection as this operation in unfrequent.
arcsToDelete = new Collection ();
}
arcsToDelete.Add (refArc);
}
refArc = arc;
}
if (arcsToDelete != null)
{
foreach (Arc arc in arcsToDelete)
{
// arc will become an orphan
DeleteTransition (arc);
}
}
}
///
/// Normalize the weights of output transitions from this state.
/// See GrammarOptimization.doc for details.
///
///
private static void NormalizeTransitionWeights (State state)
{
float flSumWeights = 0.0f;
// Compute the sum of the weights.
foreach (Arc arc in state.OutArcs)
{
flSumWeights += arc.Weight;
}
// If Sum != 0 or 1, normalize transition weights by 1/Sum.
if (!flSumWeights.Equals (0.0f) && !flSumWeights.Equals (1.0f))
{
float flNormalizationFactor = 1.0f / flSumWeights;
foreach (Arc arc in state.OutArcs)
{
arc.Weight *= flNormalizationFactor;
}
}
}
#endregion
//*******************************************************************
//
// Private Types
//
//********************************************************************
#region Private Types
#if DEBUG
// Used by the debbugger display attribute
internal class GraphDebugDisplay
{
public GraphDebugDisplay (Graph states)
{
_states = states;
}
[DebuggerBrowsable (DebuggerBrowsableState.RootHidden)]
public State [] AKeys
{
get
{
State [] states = new State [_states.Count];
int i = 0;
foreach (State state in _states)
{
states [i++] = state;
}
return states;
}
}
private Graph _states;
}
#endif
#endregion
//*******************************************************************
//
// Private Fields
//
//*******************************************************************
#region Private Fields
private State _startState;
private State _curState;
#if VIEW_STATS
static internal int _cStates = 0;
static internal int _cArcs = 0;
#endif
#endregion
}
}
// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
//------------------------------------------------------------------
//
// Copyright (c) Microsoft Corporation. All rights reserved.
//
//
// Description:
// CFG Grammar backend
//
// History:
// 5/1/2004 jeanfp Created from the Sapi Managed code
//-----------------------------------------------------------------
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Diagnostics;
using System.Globalization;
using System.Runtime.InteropServices;
using System.Text;
using System.IO;
using System.Speech.Internal.SrgsParser;
namespace System.Speech.Internal.SrgsCompiler
{
// Doubled chained linked list for fast removal of states.
// Checks are made to ensure that the State pointers are never reused.
#if DEBUG
[DebuggerDisplay ("Count = {Count}")]
[DebuggerTypeProxy (typeof (GraphDebugDisplay))]
#endif
internal class Graph : IEnumerable
{
//*******************************************************************
//
// Internal Methods
//
//*******************************************************************
#region Internal Methods
internal void Add (State state)
{
state.Init ();
if (_startState == null)
{
_curState = _startState = state;
}
else
{
_curState = _curState.Add (state);
}
}
internal void Remove (State state)
{
if (state == _startState)
{
_startState = state.Next;
}
if (state == _curState)
{
_curState = state.Prev;
}
state.Remove ();
}
IEnumerator IEnumerable.GetEnumerator ()
{
for (State item = _startState; item != null; item = item.Next)
{
yield return item;
}
}
IEnumerator IEnumerable.GetEnumerator ()
{
for (State item = _startState; item != null; item = item.Next)
{
yield return item;
}
}
///
/// Creates a new state handle in a given rule
///
///
///
/// Deletet a state
///
///
///
/// Optimizes the grammar network by removing the epsilon states and merging
/// duplicate transitions. See GrammarOptimization.doc for details.
///
internal void Optimize ()
{
foreach (State state in this)
{
NormalizeTransitionWeights (state);
}
#if DEBUG
// Remove redundant epsilon transitions.
int cStates = Count;
RemoveEpsilonStates ();
if (Count != cStates)
{
System.Diagnostics.Trace.WriteLine ("Grammar compiler, additional Epsilons could have been removed :" + (cStates - Count).ToString ());
//System.Diagnostics.Debug.Assert (_states.Count == cStates);
}
// Remove duplicate transitions.
#endif
MergeDuplicateTransitions ();
#if DEBUG
// Remove redundant epsilon transitions again now that identical epsilon transitions have been removed.
//DumpGrammarStatistics("GrammarOptimization: DuplicateRemoval");
cStates = Count;
RemoveEpsilonStates ();
//System.Diagnostics.Debug.Assert (_states.Count == cStates);
if (Count != cStates)
{
System.Diagnostics.Trace.WriteLine ("Grammar compiler, additional Epsilons could have been removed post merge transition :" + (cStates - Count).ToString ());
}
// Verify the transition weights are normalized.
//DumpGrammarStatistics ("GrammarOptimization: Final");
foreach (State state in this)
{
double flSumWeights = 0.0f; // Compute the sum of the weights.
int cArcs = 0;
foreach (Arc arc in state.OutArcs)
{
flSumWeights += arc.Weight;
cArcs++;
}
float maxWeightError = 0.00001f * cArcs;
if (flSumWeights != 0.0f && maxWeightError - Math.Abs (flSumWeights - 1.0f) < 0)
{
System.Diagnostics.Debug.Assert (true);
}
}
#endif
}
///
/// Description:
/// Change all transitions ending at SourceState to end at DestState, instead.
/// Replace references to SourceState with references to DestState before deleting SourceState.
/// - There may be additional duplicate input transitions at DestState after the move.
///
/// Assumptions:
/// - SourceState == !null, RuleInitialState, !DestState, ...
/// - DestState == null, RuleInitialState, !SourceState, ...
/// - SourceState.OutputArc.IsEmpty
/// - !(SourceState == RuleInitialState AND DestState == nul)
///
/// Algorithm:
/// - For each input transition into SourceState
/// - Transition.EndState = DestState
/// - If DestState != null, DestState.InputArcs += Transition
/// - SourceState.InputArcs -= Transition
/// - SourceState.InputArcs.Clear()
/// - If SourceState == RuleInitialState, RuleInitialState = DestState
/// - Delete SourceState
///
///
///
internal void MoveInputTransitionsAndDeleteState (State srcState, State destState)
{
System.Diagnostics.Debug.Assert (srcState != null);
System.Diagnostics.Debug.Assert (srcState != destState);
// For each input transition into SourceState, change EndState to DestState.
List arcs = srcState.InArcs.ToList ();
foreach (Arc arc in arcs)
{
// Change EndState to DestState
arc.End = destState;
}
//srcState.InArcs.RemoveRange (0,srcState.InArcs.Count);
// Replace references to SourceState with references to DestState before deleting SourceState
if (srcState.Rule._firstState == srcState) // Update RuleInitialState reference, if necessary
{
System.Diagnostics.Debug.Assert (destState != null);
srcState.Rule._firstState = destState;
}
// Delete SourceState
System.Diagnostics.Debug.Assert (srcState != null);
//System.Diagnostics.Debug.Assert (srcState.InArcs.IsEmpty);
System.Diagnostics.Debug.Assert (srcState.OutArcs.IsEmpty);
DeleteState (srcState); // Delete state from handle table
}
///
/// Description:
/// Change all transitions starting at SourceState to start at DestState, instead.
/// Deleting SourceState.
/// - The weights on the transitions have been properly adjusted.
/// The weights are not changed when moving transitions.
/// - There may be additional duplicate input transitions at DestState after the move.
///
/// Assumptions:
/// - SourceState == !null, !RuleInitialState, !DestState, ...
/// - DestState == !null, RuleInitialState, !SourceState, ...
/// - SourceState.InputArc.IsEmpty
///
/// Algorithm:
/// - For each output transition from SourceState
/// - Transition.StartState = DestState
/// - DestState.OutputArcs += Transition
/// - Delete SourceState
///
///
///
internal void MoveOutputTransitionsAndDeleteState (State srcState, State destState)
{
System.Diagnostics.Debug.Assert (srcState != null);
System.Diagnostics.Debug.Assert ((destState != null) && (destState != srcState));
System.Diagnostics.Debug.Assert (srcState.InArcs.IsEmpty);
// For each output transition from SourceState, change StartState to DestState.
List arcs = srcState.OutArcs.ToList ();
foreach (Arc arc in arcs)
{
// Change StartState to DestState
arc.Start = destState;
}
// Delete SourceState
System.Diagnostics.Debug.Assert (srcState != null);
System.Diagnostics.Debug.Assert (srcState.InArcs.IsEmpty);
//System.Diagnostics.Debug.Assert (srcState.OutArcs.IsEmpty);
DeleteState (srcState); // Delete state from handle table
}
#endregion
//********************************************************************
//
// Internal Property
//
//*******************************************************************
#region Internal Property
#if DEBUG
internal State First
{
get
{
return _startState;
}
}
internal int Count
{
get
{
int c = 0;
for (State se = _startState; se != null; se = se.Next)
{
c++;
}
return c;
}
}
#endif
#endregion
//********************************************************************
//
// Private Methods
//
//********************************************************************
#region Private Methods
#if DEBUG
///
/// Description:
/// Removing epsilon states from the grammar network.
/// See GrammarOptimization.doc for details.
/// - There may be additional duplicate transitions after removing epsilon transitions.
///
/// Algorithm:
/// - For each State in the graph,
/// - If the state has a single input epsilon transition and is not the rule initial state,
/// - Move properties to the right, if necessary.
/// - If EpsilonTransition does not have properties and is not referenced by other properties,
/// - Delete EpsilonTransition.
/// - Multiply weight of all transitions from State by EpsilonTransition.Weight.
/// - MoveOutputTransitionsAndDeleteState(State, EpsilonTransition.StartState)
/// - If the state has a single output epsilon transition,
/// - Move properties to the left, if necessary.
/// - If EpsilonTransition does not have properties and is not referenced by other properties,
/// - Delete EpsilonTransition.
/// - MoveInputTransitionsAndDeleteState(State, EpsilonTransition.EndState)
///
/// Moving SemanticTag:
/// - InputEpsilonTransitions can move its semantic tag ownerships/references to the right.
/// - OutputEpsilonTransitions can move its semantic tag ownerships/references to the left.
///
private void RemoveEpsilonStates ()
{
// For each state in the grammar graph, remove excess input/output epsilon transitions.
for (State state = First, nextState = null; state != null; state = nextState)
{
nextState = state.Next;
if (state.InArcs.CountIsOne && state.InArcs.First.IsEpsilonTransition && (state != state.Rule._firstState))
{
// State has a single input epsilon transition and is not the rule initial state.
Arc epsilonArc = state.InArcs.First;
// Attempt to move properties referencing EpsilonArc to the right.
// Optimization can only be applied when the epsilon arc is not referenced by any properties.
if (MoveSemanticTagRight (epsilonArc))
{
// Delete the input epsilon transition
State pEpsilonStartState = epsilonArc.Start;
float flEpsilonWeight = epsilonArc.Weight;
DeleteTransition (epsilonArc);
// Multiply weight of all transitions from state by EpsilonWeight.
foreach (Arc arc in state.OutArcs)
{
arc.Weight *= flEpsilonWeight;
}
// Move all output transitions from state to pEpsilonStartState and delete state if appropriate.
if (state != pEpsilonStartState)
{
MoveOutputTransitionsAndDeleteState (state, pEpsilonStartState);
}
}
}
// Optimize output epsilon transition, if possible
else if ((state.OutArcs.CountIsOne) && state.OutArcs.First.IsEpsilonTransition && (state != state.Rule._firstState))
{
// State has a single output epsilon transition
Arc epsilonArc = state.OutArcs.First;
// Attempt to move properties referencing EpsilonArc to the left.
// Optimization can only be applied when the epsilon arc is not referenced by any properties
// and when the arc does not connect RuleInitialState to null.
if (!((state == state.Rule._firstState) && (epsilonArc.End == null)) && MoveSemanticTagLeft (epsilonArc))
{
// Delete the output epsilon transition
State pEpsilonEndState = epsilonArc.End;
DeleteTransition (epsilonArc);
// Move all input transitions from state to pEpsilonEndState and delete state if appropriate.
if (state != pEpsilonEndState)
{
MoveInputTransitionsAndDeleteState (state, pEpsilonEndState);
}
}
}
}
}
#endif
///
/// Description:
/// Remove duplicate transitions starting from the same state, or ending at the same state.
/// See GrammarOptimization.doc for details.
///
/// Algorithm:
/// - Add all states to ToDoList
/// - For each state left in the ToDoList,
/// - Merge any duplicate output transitions.
/// - Add all states to ToDoList in reverse order.
/// - Remove duplicate transitions to null (special case since there is no state for FinalState)
/// - For each state left in the ToDoList,
/// - Merge any duplicate input transitions.
///
/// Notes:
/// - For best optimization, we need to move semantic properties referencing the transitions.
///
private void MergeDuplicateTransitions ()
{
List tempList = new List ();
// Build collection of states with potential identical transition.
foreach (State state in this)
{
if (state.OutArcs.ContainsMoreThanOneItem)
{
// Merge identical transitions in arcs
MergeIdenticalTransitions (state.OutArcs, tempList);
}
}
// Collection of states with potential transitions to merge
Stack mergeStates = new Stack ();
RecursiveMergeDuplicatedOutputTransition (mergeStates);
RecursiveMergeDuplicatedInputTransition (mergeStates);
}
private void RecursiveMergeDuplicatedInputTransition (Stack mergeStates)
{
// Build collection of states with potential duplicate input transitions to merge.
foreach (State state in this)
{
if (state.InArcs.ContainsMoreThanOneItem)
{
MergeDuplicateInputTransitions (state.InArcs, mergeStates);
}
}
// For each state in the collection, merge any duplicate input transitions.
List tempList = new List ();
while (mergeStates.Count > 0)
{
State state = mergeStates.Pop ();
if (state.InArcs.ContainsMoreThanOneItem)
{
// Merge identical transitions in arcs that may have been created
MergeIdenticalTransitions (state.InArcs, tempList);
MergeDuplicateInputTransitions (state.InArcs, mergeStates);
}
}
}
private void RecursiveMergeDuplicatedOutputTransition (Stack mergeStates)
{
// Build collection of states with potential duplicate output transitions to merge.
foreach (State state in this)
{
if (state.OutArcs.ContainsMoreThanOneItem)
{
MergeDuplicateOutputTransitions (state.OutArcs, mergeStates);
}
}
// For each state in the collection, merge any duplicate output transitions.
List tempList = new List ();
while (mergeStates.Count > 0)
{
State state = mergeStates.Pop ();
if (state.OutArcs.ContainsMoreThanOneItem)
{
// Merge identical transitions in arcs that may have been created
MergeIdenticalTransitions (state.OutArcs, tempList);
MergeDuplicateOutputTransitions (state.OutArcs, mergeStates);
}
}
}
///
/// Description:
/// Sort and iterate through the input arcs and remove duplicate input transitions.
/// See GrammarOptimization.doc for details.
///
/// Algorithm:
/// - MergeIdenticalTransitions(Arcs)
/// - Sort the input transitions from the state (by content and # output arcs from start state)
/// - For each set of transitions with identical content and StartState.OutputArcs.Count() == 1
/// - Move semantic properties to the left, if necessary.
/// - Label the first property-less transition as CommonArc
/// - For each successive property-less transition (DuplicateArc)
/// - Delete DuplicateArc
/// - MoveInputTransitionsAndDeleteState(DuplicateArc.StartState, CommonArc.StartState)
/// - Add CommonArc.StartState to ToDoList if not there already.
///
/// Moving SemanticTag:
/// - Duplicate input transitions can move its semantic tag ownerships/references to the left.
///
/// Collection of input transitions to collapse
/// Collection of states with potential transitions to merge
private void MergeDuplicateInputTransitions (ArcList arcs, Stack mergeStates)
{
List arcsToMerge = null;
// Reference Arc
Arc refArc = null;
bool refSet = false;
// Build a list of possible arcs to Merge
foreach (Arc arc in arcs)
{
// Skip transitions whose end state has other incoming transitions or if the end state has more than one incoming transition
bool skipTransition = arc.Start == null || !arc.Start.OutArcs.CountIsOne;
// Find next set of duplicate output transitions (potentially with properties).
if (refArc != null && Arc.CompareContent (arc, refArc) == 0)
{
if (!skipTransition)
{
// Lazy init as entering this loop is a rare event
if (arcsToMerge == null)
{
arcsToMerge = new List ();
}
// Add the first element
if (!refSet)
{
arcsToMerge.Add (refArc);
refSet = true;
}
arcsToMerge.Add (arc);
}
}
else
{
// New word, reset everything
refArc = skipTransition ? null : arc;
refSet = false;
}
}
// Combine the arcs if possible
if (arcsToMerge != null)
{
// Sort the arc per content and output transition
arcsToMerge.Sort (Arc.CompareForDuplicateInputTransitions);
refArc = null;
Arc commonArc = null; // Common property-less transition to merge into
State commonStartState = null;
bool fCommonStartStateChanged = false; // Did CommonStartState change and need re-optimization?
foreach (Arc arc in arcsToMerge)
{
if (refArc == null || Arc.CompareContent (arc, refArc) != 0)
{
// Purge the last operations and reset all the local
refArc = arc;
// If CommonStartState changed, renormalize weights and add it to MergeStates for reoptimization.
if (fCommonStartStateChanged)
{
AddToMergeStateList (mergeStates, commonStartState);
}
// Reset the arcs
commonArc = null;
commonStartState = null;
fCommonStartStateChanged = false;
}
// For each property-less duplicate transition
Arc duplicatedArc = arc;
State duplicatedStartState = duplicatedArc.Start;
// Attempt to move properties referencing duplicate arc to the right.
// Optimization can only be applied when the duplicate arc is not referenced by any properties
// and the duplicate end state is not the RuleOutitalState.
if (MoveSemanticTagLeft (duplicatedArc))
{
// duplicatedArc != commonArc
if (commonArc != null)
{
if (!fCommonStartStateChanged)
{
// Processing first duplicate arc.
// Multiply the weights of transitions from CommonStartState by CommonArc.Weight.
foreach (Arc arcOut in commonStartState.OutArcs)
{
arcOut.Weight *= commonArc.Weight;
}
fCommonStartStateChanged = true; // Output transitions of CommonStartState changed.
}
// Multiply the weights of transitions from DuplicateStartState by DuplicateArc.Weight.
foreach (Arc arcOut in duplicatedStartState.OutArcs)
{
arcOut.Weight *= duplicatedArc.Weight;
}
duplicatedArc.Weight += commonArc.Weight;// Merge duplicate arc weight with common arc
Arc.CopyTags (commonArc, duplicatedArc, Direction.Left);
DeleteTransition (commonArc); // Delete successive duplicate transitions
// Move outputs of duplicate state to common state; Delete duplicate state
MoveInputTransitionsAndDeleteState (commonStartState, duplicatedStartState);
}
// Label first property-less transition as CommonArc
commonArc = duplicatedArc;
commonStartState = duplicatedStartState;
}
}
// If CommonStartState changed, renormalize weights and add it to MergeStates for reoptimization.
if (fCommonStartStateChanged)
{
AddToMergeStateList (mergeStates, commonStartState);
}
}
}
///
/// Description:
/// Sort and iterate through the output arcs and remove duplicate output transitions.
/// See GrammarOptimization.doc for details.
///
/// Algorithm:
/// - MergeIdenticalTransitions(Arcs)
/// - Sort the output transitions from the state (by content and # input arcs from end state)
/// - For each set of transitions with identical content, EndState != null, and EndState.InputArcs.Count() == 1
/// - Move semantic properties to the right, if necessary.
/// - Label the first property-less transition as CommonArc
/// - For each property-less transition (DuplicateArc) including CommonArc
/// - Multiply the weights of output transitions from DuplicateArc.EndState by DuplicateArc.Weight.
/// - If DuplicateArc != CommonArc
/// - CommonArc.Weight += DuplicateArc.Weight
/// - Delete DuplicateArc
/// - MoveOutputTransitionsAndDeleteState(DuplicateArc.EndState, CommonArc.EndState)
/// - Normalize weights of output transitions from CommonArc.EndState.
/// - Add CommonArc.EndtState to ToDoList if not there already.
///
/// Moving SemanticTag:
/// - Duplicate output transitions can move its semantic tag ownerships/references to the right.
///
/// Collection of output transitions to collapse
/// Collection of states with potential transitions to merge
private void MergeDuplicateOutputTransitions (ArcList arcs, Stack mergeStates)
{
List arcsToMerge = null;
// Reference Arc
Arc refArc = null;
bool refSet = false;
// Build a list of possible arcs to Merge
foreach (Arc arc in arcs)
{
// Skip transitions whose end state has other incoming transitions or if the end state has more than one incoming transition
bool skipTransition = arc.End == null || !arc.End.InArcs.CountIsOne;
// Find next set of duplicate output transitions (potentially with properties).
if (refArc != null && Arc.CompareContent (arc, refArc) == 0)
{
if (!skipTransition)
{
// Lazy init as entering this loop is a rare event
if (arcsToMerge == null)
{
arcsToMerge = new List ();
}
// Add the first element
if (!refSet)
{
arcsToMerge.Add (refArc);
refSet = true;
}
arcsToMerge.Add (arc);
}
}
else
{
// New word, reset everything
refArc = skipTransition ? null : arc;
refSet = false;
}
}
// Combine the arcs if possible
if (arcsToMerge != null)
{
// Sort the arc per content and output transition
arcsToMerge.Sort (Arc.CompareForDuplicateOutputTransitions);
refArc = null;
Arc commonArc = null; // Common property-less transition to merge into
State commonEndState = null;
bool fCommonEndStateChanged = false; // Did CommonEndState change and need re-optimization?
foreach (Arc arc in arcsToMerge)
{
if (refArc == null || Arc.CompareContent (arc, refArc) != 0)
{
// Purge the last operations and reset all the local
refArc = arc;
// If CommonEndState changed, renormalize weights and add it to MergeStates for reoptimization.
if (fCommonEndStateChanged)
{
AddToMergeStateList (mergeStates, commonEndState);
}
// Reset the arcs
commonArc = null;
commonEndState = null;
fCommonEndStateChanged = false;
}
// For each property-less duplicate transition
Arc duplicatedArc = arc;
State duplicatedEndState = duplicatedArc.End;
// Attempt to move properties referencing duplicate arc to the right.
// Optimization can only be applied when the duplicate arc is not referenced by any properties
// and the duplicate end state is not the RuleInitalState.
if ((duplicatedEndState != duplicatedEndState.Rule._firstState) && MoveSemanticTagRight (duplicatedArc))
{
// duplicatedArc != commonArc
if (commonArc != null)
{
if (!fCommonEndStateChanged)
{
// Processing first duplicate arc.
// Multiply the weights of transitions from CommonEndState by CommonArc.Weight.
foreach (Arc arcOut in commonEndState.OutArcs)
{
arcOut.Weight *= commonArc.Weight;
}
fCommonEndStateChanged = true; // Output transitions of CommonEndState changed.
}
// Multiply the weights of transitions from DuplicateEndState by DuplicateArc.Weight.
foreach (Arc arcOut in duplicatedEndState.OutArcs)
{
arcOut.Weight *= duplicatedArc.Weight;
}
duplicatedArc.Weight += commonArc.Weight;// Merge duplicate arc weight with common arc
Arc.CopyTags (commonArc, duplicatedArc, Direction.Right);
DeleteTransition (commonArc); // Delete successive duplicate transitions
// Move outputs of duplicate state to common state; Delete duplicate state
MoveOutputTransitionsAndDeleteState (commonEndState, duplicatedEndState);
}
// Label first property-less transition as CommonArc
commonArc = duplicatedArc;
commonEndState = duplicatedEndState;
}
}
// If CommonEndState changed, renormalize weights and add it to MergeStates for reoptimization.
if (fCommonEndStateChanged)
{
AddToMergeStateList (mergeStates, commonEndState);
}
}
}
private static void AddToMergeStateList (Stack mergeStates, State commonEndState)
{
NormalizeTransitionWeights (commonEndState);
if (!mergeStates.Contains (commonEndState))
{
mergeStates.Push (commonEndState);
}
}
///
/// Move any semantic tag ownership and optionally references to a unique
/// previous arc, if possible.
///
/// MoveReferences = true: Return if arc is propertyless after the move.
/// MoveReferences = false: Return if arc does not own semantic tag after the move.
/// The arc can still be referenced by other semantic tags.
///
///
///
/// Move any semantic tag ownership and optionally references to a unique
/// next arc, if possible.
///
/// MoveReferences = true: Return if arc is propertyless after the move.
/// MoveReferences = false: Return if arc does not own semantic tag after the move.
/// The arc can still be referenced by other semantic tags.
///
/// Force semantic tag references to always move with tag. See 37583.
/// This changes the range of words spanned by the tag, which is a bug for SAPI grammars.
///
///
///
/// Check if tags can be moved from a source arc to a destination
/// - Semantic interpretation. Tags cannot be moved if they would end up over a rule ref.
/// - Sapi properties. Tag can be put anywhere.
///
///
///
///
/// Description:
/// Detach and delete the specified transition from the graph.
/// Relocate or delete referencing semantic tags before deleting the transition.
///
/// Special Case:
/// Arc.EndState == null
/// Arc.Optional == true
///
///
private static void DeleteTransition (Arc arc)
{
// Arc cannot own SemanticTag
System.Diagnostics.Debug.Assert (arc.SemanticTagCount == 0);
// Arc cannot be referenced by SemanticTags
System.Diagnostics.Debug.Assert (arc.IsPropertylessTransition);
// Detach arc from start and end state
arc.Start = arc.End = null;
}
///
/// Description:
/// Merge identical transitions with identical content, StartState, and EndState.
///
///
///
///
private static void MergeIdenticalTransitions (ArcList arcs, List identicalWords)
{
// Need at least two transitions to merge.
System.Diagnostics.Debug.Assert (arcs.ContainsMoreThanOneItem);
// Need at least two transitions to merge.
List> segmentsToDelete = null;
Arc refArc = arcs.First;
// Accumulate a set of transition to delete
foreach (Arc arc in arcs)
{
if (Arc.CompareContent (refArc, arc) != 0)
{
// Identical transition
if (identicalWords.Count >= 2)
{
identicalWords.Sort (Arc.CompareIdenticalTransitions);
if (segmentsToDelete == null)
{
segmentsToDelete = new List> ();
}
// Add the list of same words into a list for further processing.
// The expectation of having an identical transition is very low so the code
// may be a bit slow.
segmentsToDelete.Add (new List (identicalWords));
}
identicalWords.Clear ();
}
refArc = arc;
identicalWords.Add (arc);
}
// Did the last word was replicated several times?
if (identicalWords.Count >= 2)
{
MergeIdenticalTransitions (identicalWords);
}
identicalWords.Clear ();
// Process the accumulated words
if (segmentsToDelete != null)
{
foreach (List segmentToDelete in segmentsToDelete)
{
MergeIdenticalTransitions (segmentToDelete);
}
}
}
///
/// Description:
/// Merge identical transitions with identical content, StartState, and EndState.
///
/// Algorithm:
/// - LastArc = Arcs[0]
/// - For each Arc in Arcs[1-],
/// - If Arc is identical to LastArc,
/// - LastArc.Weight += Arc.Weight
/// - Delete Arc
/// - Else LastArc = Arc
///
/// Moving SemanticTag:
/// - Identical transitions have identical semantic tags. Currently impossible to have identical
/// non-null tags.
/// - MoveSemanticTagReferences(DuplicateArc, CommonArc)
///
///
private static void MergeIdenticalTransitions (List identicalWords)
{
Collection arcsToDelete = null;
Arc refArc = null;
foreach (Arc arc in identicalWords)
{
if (refArc != null && Arc.CompareIdenticalTransitions (refArc, arc) == 0)
{
// Identical transition
arc.Weight += refArc.Weight;
refArc.ClearTags ();
if (arcsToDelete == null)
{
// delay the creation of the collection as this operation in unfrequent.
arcsToDelete = new Collection ();
}
arcsToDelete.Add (refArc);
}
refArc = arc;
}
if (arcsToDelete != null)
{
foreach (Arc arc in arcsToDelete)
{
// arc will become an orphan
DeleteTransition (arc);
}
}
}
///
/// Normalize the weights of output transitions from this state.
/// See GrammarOptimization.doc for details.
///
///
private static void NormalizeTransitionWeights (State state)
{
float flSumWeights = 0.0f;
// Compute the sum of the weights.
foreach (Arc arc in state.OutArcs)
{
flSumWeights += arc.Weight;
}
// If Sum != 0 or 1, normalize transition weights by 1/Sum.
if (!flSumWeights.Equals (0.0f) && !flSumWeights.Equals (1.0f))
{
float flNormalizationFactor = 1.0f / flSumWeights;
foreach (Arc arc in state.OutArcs)
{
arc.Weight *= flNormalizationFactor;
}
}
}
#endregion
//*******************************************************************
//
// Private Types
//
//********************************************************************
#region Private Types
#if DEBUG
// Used by the debbugger display attribute
internal class GraphDebugDisplay
{
public GraphDebugDisplay (Graph states)
{
_states = states;
}
[DebuggerBrowsable (DebuggerBrowsableState.RootHidden)]
public State [] AKeys
{
get
{
State [] states = new State [_states.Count];
int i = 0;
foreach (State state in _states)
{
states [i++] = state;
}
return states;
}
}
private Graph _states;
}
#endif
#endregion
//*******************************************************************
//
// Private Fields
//
//*******************************************************************
#region Private Fields
private State _startState;
private State _curState;
#if VIEW_STATS
static internal int _cStates = 0;
static internal int _cArcs = 0;
#endif
#endregion
}
}
// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
Link Menu
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- DesignerActionHeaderItem.cs
- StructureChangedEventArgs.cs
- FrameDimension.cs
- DataGridSortCommandEventArgs.cs
- WebConfigurationHost.cs
- ContainerUIElement3D.cs
- WindowsAuthenticationEventArgs.cs
- CharKeyFrameCollection.cs
- XmlSubtreeReader.cs
- CommandDevice.cs
- SerialErrors.cs
- PropertyMapper.cs
- embossbitmapeffect.cs
- DataGridColumnEventArgs.cs
- DataKey.cs
- TableStyle.cs
- HybridWebProxyFinder.cs
- SmiEventSink.cs
- Events.cs
- MessageLogTraceRecord.cs
- MaterialGroup.cs
- Ops.cs
- ArraySortHelper.cs
- AttachmentCollection.cs
- SequentialUshortCollection.cs
- IODescriptionAttribute.cs
- SystemUnicastIPAddressInformation.cs
- QilBinary.cs
- PropertyValueChangedEvent.cs
- XhtmlBasicLiteralTextAdapter.cs
- IndexedString.cs
- InsufficientMemoryException.cs
- UxThemeWrapper.cs
- ButtonColumn.cs
- CannotUnloadAppDomainException.cs
- RootAction.cs
- WebPartChrome.cs
- IPEndPoint.cs
- BamlStream.cs
- MenuItemStyle.cs
- SqlServices.cs
- StylusOverProperty.cs
- dataSvcMapFileLoader.cs
- MessageQueuePermission.cs
- TemplateKey.cs
- DeleteStoreRequest.cs
- TemplateControlParser.cs
- FileClassifier.cs
- DesignConnection.cs
- CodeMemberEvent.cs
- CodeNamespace.cs
- ExceptionTrace.cs
- XhtmlBasicValidationSummaryAdapter.cs
- WorkflowOwnershipException.cs
- WebPartCatalogAddVerb.cs
- MouseActionValueSerializer.cs
- NotifyCollectionChangedEventArgs.cs
- HtmlControlAdapter.cs
- DbConnectionOptions.cs
- QilBinary.cs
- DynamicFilter.cs
- ModelVisual3D.cs
- RenderTargetBitmap.cs
- UniqueContractNameValidationBehavior.cs
- ToolboxCategory.cs
- PersonalizationEntry.cs
- CapabilitiesState.cs
- HttpListenerContext.cs
- VisualStyleRenderer.cs
- DNS.cs
- FreezableOperations.cs
- ProcessingInstructionAction.cs
- SQLChars.cs
- MailWebEventProvider.cs
- WebPartActionVerb.cs
- SapiRecoContext.cs
- BaseDataList.cs
- EntityClientCacheKey.cs
- NameNode.cs
- TextServicesDisplayAttribute.cs
- TextTreeObjectNode.cs
- KeysConverter.cs
- DoubleCollectionValueSerializer.cs
- OledbConnectionStringbuilder.cs
- LinqDataSourceContextEventArgs.cs
- Debug.cs
- XmlHierarchyData.cs
- FormsAuthenticationTicket.cs
- HorizontalAlignConverter.cs
- HTTP_SERVICE_CONFIG_URLACL_KEY.cs
- Rect3D.cs
- StaticExtensionConverter.cs
- ChannelPoolSettingsElement.cs
- SafeRegistryKey.cs
- SecurityCookieModeValidator.cs
- SelectingProviderEventArgs.cs
- XslAst.cs
- Events.cs
- EventRecord.cs
- SamlSecurityTokenAuthenticator.cs