- Main Page
- Classes
- Files

- File List

# C:/Users/Andreas Schiffler/Desktop/SVN/NewGamePhysics/NewGamePhysics/Mathematics/ValueUnbiaser.cs

    00001 ﻿//-----------------------------------------------------------------------------
    00002 // ValueUnbiaser.cs
    00003 // (A. Schiffler, 2009)
    00004 //-----------------------------------------------------------------------------
    00005
    00006 namespace NewGamePhysics.Mathematics
    00007 {
    00008     using System;
    00009     using System.Collections.Generic;
    00010     using System.Text;
    00011
    00015     public enum ValueUnbiasAlgorithm
    00016     {
    00021         Pairwise,
    00022
    00027         Median,
    00028
    00033         Partition,
    00034     }
    00035
    00039     public class ValueUnbiaser
    00040     {
    00044         private ValueUnbiasAlgorithm algorithm;
    00045
    00049         private BitUnbiaser bitUnbiaser;
    00050
    00056         public ValueUnbiaser(ValueUnbiasAlgorithm algorithm)
    00057         {
    00058             this.algorithm = algorithm;
    00059
    00060             // Create AMLS unbiaser for partitioning technique
    00061             this.bitUnbiaser = new BitUnbiaser(BitUnbiasAlgorithm.AMLS);
    00062         }
    00063
    00071         public string Extract(double[] uncorrelatedData)
    00072         {
    00073             if (uncorrelatedData.Length < 2)
    00074             {
    00075                 return string.Empty;
    00076             }
    00077
    00078             StringBuilder sb = new StringBuilder();
    00079
    00080             // Calculate intervals between data values
    00081             double[] intervals = new double[uncorrelatedData.Length - 1];
    00082             for (int i = 0; i < intervals.Length; i++)
    00083             {
    00084                 intervals[i] = uncorrelatedData[i + 1] - uncorrelatedData[i];
    00085             }
    00086
    00087             // Unbias using selected algorithm
    00088             switch (this.algorithm)
    00089             {
    00090                 case ValueUnbiasAlgorithm.Pairwise:
    00091                     this.PairwiseExtract(intervals, ref sb);
    00092                     break;
    00093                 case ValueUnbiasAlgorithm.Median:
    00094                     this.MedianExtract(intervals, ref sb);
    00095                     break;
    00096                 case ValueUnbiasAlgorithm.Partition:
    00097                     this.RecursiveExtract(intervals, ref sb);
    00098                     break;
    00099             }
    00100
    00101             // Return collected bits
    00102             return sb.ToString();
    00103         }
    00104
    00111         private static void Swap<T>(ref T item1, ref T item2)
    00112         {
    00113             T temp = item1;
    00114             item1 = item2;
    00115             item2 = temp;
    00116         }
    00117
    00123         private void PairwiseExtract(double[] intervals, ref StringBuilder collector)
    00124         {
    00125             if (intervals.Length < 3)
    00126             {
    00127                 return;
    00128             }
    00129
    00130             int currentPos = 0;
    00131             int lastPos = intervals.Length - 2;
    00132             int swap = 0;
    00133             do
    00134             {
    00135
    00136                 double dt1 = intervals[currentPos++];
    00137                 double dt2 = intervals[currentPos++];
    00138
    00139                 // Local unbias by swapping order
    00140                 if (swap == 0)
    00141                 {
    00142                     Swap<double>(ref dt1, ref dt2);
    00143                     swap++;
    00144                 }
    00145                 else
    00146                 {
    00147                     swap = 0;
    00148                 }
    00149
    00150                 // Add bits only when intervals differ
    00151                 if (dt1 < dt2)
    00152                 {
    00153                     collector.Append('0');
    00154                 }
    00155                 else if (dt1 > dt2)
    00156                 {
    00157                     collector.Append('1');
    00158                 }
    00159
    00160                 currentPos += 2;
    00161             }
    00162             while (currentPos <= lastPos);
    00163         }
    00164
    00171         private void MedianExtract(double[] intervals, ref StringBuilder collector)
    00172         {
    00173             if (intervals.Length < 3)
    00174             {
    00175                 return;
    00176             }
    00177
    00178             // Determine median interval
    00179             double[] sortedIntervals = new double[intervals.Length];
    00180             intervals.CopyTo(sortedIntervals, 0);
    00181             Array.Sort(sortedIntervals);
    00182
    00183             double medianLow;
    00184             double medianHigh;
    00185             if ((intervals.Length & 1) == 1)
    00186             {
    00187                 // Odd number of elements, take middle value
    00188                 medianLow = sortedIntervals[(intervals.Length - 1) / 2];
    00189                 medianHigh = medianLow;
    00190             }
    00191             else
    00192             {
    00193                 // Even number of elements take both values in the center
    00194                 medianLow = sortedIntervals[intervals.Length / 2 - 1];
    00195                 medianHigh = sortedIntervals[intervals.Length / 2];
    00196             }
    00197
    00198             // Generate bits using median values, excluding
    00199             // the median itself
    00200             for (int i = 0; i < intervals.Length; i++)
    00201             {
    00202                 if (intervals[i] < medianLow)
    00203                 {
    00204                     collector.Append('0');
    00205                 }
    00206                 else if (intervals[i] > medianHigh)
    00207                 {
    00208                     collector.Append('1');
    00209                 }
    00210             }
    00211         }
    00212
    00219         private void RecursiveExtract(double[] intervals, ref StringBuilder collector)
    00220         {
    00221             if (intervals.Length < 3)
    00222             {
    00223                 return;
    00224             }
    00225
    00226             // Pick first value as pivot
    00227             double pivot = intervals[0];
    00228
    00229             // Compile list of all non-pivot integers
    00230             List<double> nonPivotData = new List<double>();
    00231             for (int i = 1; i < intervals.Length; i++)
    00232             {
    00233                 if (intervals[i] != pivot)
    00234                 {
    00235                     nonPivotData.Add(intervals[i]);
    00236                 }
    00237             }
    00238
    00239             // Early finish
    00240             if (nonPivotData.Count == 0)
    00241             {
    00242                 return;
    00243             }
    00244
    00245             StringBuilder amlsData;
    00246
    00247             // Get bits (part 1)
    00248             amlsData = new StringBuilder();
    00249             for (int i = 1; i < intervals.Length; i++)
    00250             {
    00251                 amlsData.Append((intervals[i] == pivot) ? '1' : '0');
    00252             }
    00253
    00254             if (amlsData.Length > 1)
    00255             {
    00256                 collector.Append(this.bitUnbiaser.Process(amlsData.ToString()));
    00257             }
    00258
    00259             // Get bits (part 2)
    00260             amlsData = new StringBuilder();
    00261             for (int i = 0; i < nonPivotData.Count; i++)
    00262             {
    00263                 amlsData.Append((nonPivotData[i] < pivot) ? '1' : '0');
    00264             }
    00265
    00266             if (amlsData.Length > 1)
    00267             {
    00268                 collector.Append(this.bitUnbiaser.Process(amlsData.ToString()));
    00269             }
    00270
    00271             // Split data for recursion
    00272             List<double> left = new List<double>();
    00273             List<double> right = new List<double>();
    00274             for (int i = 1; i < nonPivotData.Count; i++)
    00275             {
    00276                 if (nonPivotData[i] < pivot)
    00277                 {
    00278                     left.Add(nonPivotData[i]);
    00279                 }
    00280                 else
    00281                 {
    00282                     right.Add(nonPivotData[i]);
    00283                 }
    00284             }
    00285
    00286             // Recurse
    00287             RecursiveExtract(left.ToArray(), ref collector);
    00288             RecursiveExtract(right.ToArray(), ref collector);
    00289         }
    00290     }
    00291 }