source: trunk/CrypPlugins/CostFunction/CostFunction.cs @ 850

Last change on this file since 850 was 850, checked in by kopal, 12 years ago

profiled cost function (coincidence/entropy), some time optimization

File size: 18.8 KB
Line 
1/*                             
2   Copyright 2009 Team CrypTool (Sven Rech,Dennis Nolte,Raoul Falk,Nils Kopal), Uni Duisburg-Essen
3
4   Licensed under the Apache License, Version 2.0 (the "License");
5   you may not use this file except in compliance with the License.
6   You may obtain a copy of the License at
7
8       http://www.apache.org/licenses/LICENSE-2.0
9
10   Unless required by applicable law or agreed to in writing, software
11   distributed under the License is distributed on an "AS IS" BASIS,
12   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   See the License for the specific language governing permissions and
14   limitations under the License.
15*/
16
17using System;
18using System.Collections.Generic;
19using System.Linq;
20using System.Text;
21using Cryptool.PluginBase.Cryptography;
22using Cryptool.PluginBase;
23using Cryptool.PluginBase.Miscellaneous;
24using Cryptool.PluginBase.Analysis;
25using System.ComponentModel;
26using Cryptool.PluginBase.Control;
27using System.IO;
28namespace Cryptool.Plugins.CostFunction
29{
30    [Author("Nils Kopal", "Nils.Kopal@cryptool.org", "Uni Duisburg-Essen", "http://www.uni-due.de")]
31    [PluginInfo(false, "CostFunction", "CostFunction", null, "CostFunction/icon.png")]
32    public class CostFunction : IAnalysisMisc
33    {
34        #region private variables
35        private CostFunctionSettings settings = new CostFunctionSettings();
36        private byte[] inputText = null;
37        private byte[] outputText = null;
38        private double value = 0;
39        private Boolean stopped = true;
40        private IControlCost controlSlave;
41        private String bigramInput;
42               
43
44
45        private IDictionary<int, IDictionary<string, double[]>> statistics;
46     
47        #endregion
48        #region internal constants
49        internal const int ABSOLUTE = 0;
50        internal const int PERCENTAGED = 1;
51        internal const int LOG2 = 2;
52        internal const int SINKOV = 3;
53        #endregion
54        #region CostFunctionInOut
55
56        [PropertyInfo(Direction.InputData, "Text Input", "Input your Text here", "", DisplayLevel.Beginner)]
57        public byte[] InputText
58        {
59            get
60            {
61                return inputText;
62            }
63            set
64            {
65                this.inputText = value;               
66                OnPropertyChanged("InputText");
67            }
68        }
69
70        [PropertyInfo(Direction.OutputData, "Text Output", "Your Text will be send here", "", DisplayLevel.Beginner)]
71        public byte[] OutputText
72        {
73            get
74            {
75                return outputText;
76            }
77            set
78            {
79                this.outputText = value;               
80                OnPropertyChanged("OutputText");
81            }
82        }
83
84        [PropertyInfo(Direction.OutputData, "Value", "The value of the function will be send here", "", DisplayLevel.Beginner)]
85        public double Value
86        {
87            get
88            {
89                return value;
90            }
91            set
92            {
93                this.value = value;
94                OnPropertyChanged("Value");
95            }
96        }
97               
98        [PropertyInfo(Direction.ControlSlave, "SDES Slave", "Direct access to SDES.", "", DisplayLevel.Beginner)]
99        public IControlCost ControlSlave
100        {
101            get
102            {
103                if (controlSlave == null)
104                    controlSlave = new CostFunctionControl(this);
105                return controlSlave;
106            }
107        } 
108
109        #endregion
110
111        #region IPlugin Members
112
113        public event GuiLogNotificationEventHandler OnGuiLogNotificationOccured;
114        public event PluginProgressChangedEventHandler OnPluginProgressChanged;
115       
116
117        public ISettings Settings
118        {
119            get { return this.settings; }
120            set { this.settings = (CostFunctionSettings)value; }
121        }
122
123        public System.Windows.Controls.UserControl Presentation
124        {
125            get { return null; }
126        }
127
128        public System.Windows.Controls.UserControl QuickWatchPresentation
129        {
130            get { return null; }
131        }
132
133        public void PreExecution()
134        {
135            this.stopped = false;
136        }
137
138        public void Execute()
139        {
140            if (this.InputText is Object && this.stopped == false)
141            {
142                int bytesToUse = 0;
143                try
144                {
145                    bytesToUse = int.Parse(settings.BytesToUse);
146                }
147                catch (Exception ex)
148                {
149                    GuiLogMessage("Entered bytesToUse is not an integer: " + ex.Message, NotificationLevel.Error);
150                    return;
151                }
152
153                if (bytesToUse > this.InputText.Length)
154                {
155                    bytesToUse = 0;
156                }
157
158                byte[] array;
159
160                if (bytesToUse > 0)
161                {
162                    //Create a new Array of size of bytesToUse if needed
163                    array = new byte[bytesToUse];
164                    for (int i = 0; i < bytesToUse && i < this.InputText.Length; i++)
165                    {
166                        array[i] = InputText[i];
167                    }
168                }
169                else
170                {
171                    array = this.InputText;
172                }
173
174                ProgressChanged(0.5, 1); 
175                bigramInput = ByteArrayToString(array);
176                switch (settings.FunctionType)
177                {
178
179                    case 0: // Index of Coincedence
180                        this.Value = calculateIndexOfCoincidence(array);
181                        break;
182
183                    case 1: // Entropy
184                        this.Value = calculateEntropy(array);
185                        break;
186
187                    case 2: // Log 2 Bigrams
188                        this.Value = calculateNGrams(bigramInput,2,2);
189                        break;
190
191                    case 3: // sinkov Bigrams
192                        this.Value = calculateNGrams(bigramInput,2,3);
193                        break;
194                    case 4: //percentaged Bigrams
195                        this.Value = calculateNGrams(bigramInput,2,1);
196                        break;
197                    default:
198                        this.Value = -1;
199                        break;
200                }//end switch               
201 
202                this.OutputText = this.InputText;
203                ProgressChanged(1, 1);   
204
205            }//end if
206           
207        }//end Execute
208
209        public void PostExecution()
210        {
211            this.stopped = true;
212        }
213
214        public void Pause()
215        {
216           
217        }
218
219        public void Stop()
220        {
221            this.stopped = false;
222        }
223
224        public void Initialize()
225        {
226
227        }
228
229        public void Dispose()
230        {
231           
232        }
233
234        #endregion     
235
236        #region INotifyPropertyChanged Members
237
238        public event System.ComponentModel.PropertyChangedEventHandler PropertyChanged;
239
240        public void OnPropertyChanged(string name)
241        {
242            EventsHelper.PropertyChanged(PropertyChanged, this, new PropertyChangedEventArgs(name));
243        }
244
245        private void ProgressChanged(double value, double max)
246        {
247            EventsHelper.ProgressChanged(OnPluginProgressChanged, this, new PluginProgressEventArgs(value, max));
248        }
249
250        public void GuiLogMessage(string p, NotificationLevel notificationLevel)
251        {
252            EventsHelper.GuiLogMessage(OnGuiLogNotificationOccured, this, new GuiLogEventArgs(p, this, notificationLevel));
253        }
254
255        #endregion
256
257        #region IPlugin Members
258
259        public event StatusChangedEventHandler OnPluginStatusChanged;
260
261        #endregion
262
263        #region private methods
264
265        /// <summary>
266        /// Calculates the Index of Coincidence multiplied with 100 of
267        /// a given byte array
268        ///
269        /// for example a German text has about 7.62
270        ///           an English text has about 6.61
271        /// </summary>
272        /// <param name="text">text to use</param>
273        /// <returns>Index of Coincidence</returns>
274        public double calculateIndexOfCoincidence(byte[] text)
275        {
276            return calculateIndexOfCoincidence(text, text.Length);
277        }
278
279        /// <summary>
280        /// Calculates the Index of Coincidence multiplied with 100 of
281        /// a given byte array
282        ///
283        /// for example a German text has about 7.62
284        ///           an English text has about 6.61
285        /// </summary>
286        /// <param name="text">text to use</param>
287        /// <param name="text">bytesToUse</param>
288        /// <returns>Index of Coincidence</returns>
289        public double calculateIndexOfCoincidence(byte[] text, int bytesToUse)
290        {
291            if (bytesToUse > text.Length)
292                bytesToUse = text.Length;
293
294            double[] n = new double[256];
295            //count all ASCII symbols
296            int counter = 0;
297            foreach (byte b in text)
298            {
299                    n[b]++;
300                    counter++;
301                    if (counter == bytesToUse)
302                        break;
303            }
304
305            double coindex = 0;
306            //sum them
307            for (int i = 0; i < n.Length; i++)
308            {
309                coindex = coindex + n[i] * (n[i] - 1);               
310            }
311
312            coindex = coindex / (bytesToUse);
313            coindex = coindex / (bytesToUse - 1);
314
315            return coindex * 100;
316
317        }//end calculateIndexOfCoincidence
318
319        /// <summary>
320        /// Calculates the Entropy of a given byte array
321        /// for example a German text has about 4.0629
322        /// </summary>
323        /// <param name="text">text to use</param>
324        /// <returns>Entropy</returns>
325        public double calculateEntropy(byte[] text)
326        {
327            return calculateEntropy(text, text.Length);
328        }
329
330        /// <summary>
331        /// Calculates the Entropy of a given byte array
332        /// for example a German text has about 4.0629
333        /// </summary>
334        /// <param name="text">text to use</param>
335        /// <returns>Entropy</returns>
336        public double calculateEntropy(byte[] text, int bytesToUse)
337        {
338            if (bytesToUse > text.Length)
339                bytesToUse = text.Length;
340
341            double[] n = new double[256];
342            //count all ASCII symbols
343            int counter = 0;
344            foreach (byte b in text)
345            {
346                    n[b]++;
347                    counter++;
348                    if (counter == bytesToUse)
349                        break;
350            }
351
352            double entropy = 0;
353            //calculate probabilities and sum entropy
354            for (int i = 0; i < n.Length; i++)
355            {
356                double pz = n[i] / bytesToUse; //probability of character n[i]
357                if (pz > 0)
358                    entropy = entropy + pz * Math.Log(pz, 2);
359            }
360
361            return -1 * entropy; // because of log we have negative values, but we want positive
362
363        }//end calculateEntropy
364
365
366        /// <summary>
367        /// This method calculates a trigram log2 score of a given text on the basis of a given grams dictionary.
368        /// Case is insensitive.
369        /// </summary>
370        /// <param name="input">The text to be scored</param>
371        /// <param name="length">n-gram length</param>
372        /// <returns>The trigram score result</returns>
373        public double calculateNGrams(string input, int length, int valueSelection)
374        {
375            this.statistics = new Dictionary<int, IDictionary<string, double[]>>();
376            double score = 0;
377            IDictionary<string, double[]> corpusGrams = GetStatistics(length);
378
379            // FIXME: case handling?
380
381            HashSet<string> inputGrams = new HashSet<string>();
382
383            foreach (string g in GramTokenizer.tokenize(input, length, false))
384            {
385                // ensure each n-gram is counted only once
386                if (inputGrams.Add(g))
387                {
388                    if (corpusGrams.ContainsKey(g))
389                    {
390                        score += corpusGrams[g][valueSelection];
391                        GuiLogMessage(input, NotificationLevel.Info);
392           
393                    }
394                }
395            }
396            return score;
397        }
398        public IDictionary<string, double[]> GetStatistics(int gramLength)
399        {
400            // FIXME: inputTriGrams is not being used!
401
402            // FIXME: implement exception handling
403            if (!statistics.ContainsKey(gramLength))
404            {
405                GuiLogMessage("Trying to load default statistics for " + gramLength + "-grams", NotificationLevel.Info);
406                statistics[gramLength] = LoadDefaultStatistics(gramLength);               
407            }
408
409            return statistics[gramLength];
410        }
411
412
413        private IDictionary<string, double[]> LoadDefaultStatistics(int length)
414        {
415            Dictionary<string, double[]> grams = new Dictionary<string, double[]>();
416
417            StreamReader reader = new StreamReader(Path.Combine(PluginResource.directoryPath, GetStatisticsFilename(length)));
418
419            string line;
420            while ((line = reader.ReadLine()) != null)
421            {
422                if (line.StartsWith("#"))
423                    continue;
424
425                string[] tokens = WordTokenizer.tokenize(line).ToArray();
426                if (tokens.Length == 0)
427                    continue;
428                //Debug.Assert(tokens.Length == 2, "Expected 2 tokens, found " + tokens.Length + " on one line");
429
430                grams.Add(tokens[0], new double[] { Double.Parse(tokens[1]), 0, 0, 0 });
431            }
432
433            double sum = grams.Values.Sum(item => item[ABSOLUTE]);
434            GuiLogMessage("Sum of all n-gram counts is: " + sum, NotificationLevel.Debug);
435
436            // calculate scaled values
437            foreach (double[] g in grams.Values)
438            {
439                g[PERCENTAGED] = g[ABSOLUTE] / sum;
440                g[LOG2] = Math.Log(g[ABSOLUTE], 2);
441                g[SINKOV] = Math.Log(g[PERCENTAGED], Math.E);
442            }
443
444            return grams;
445        }
446
447        /// <summary>
448        /// Get file name for default n-gram frequencies.
449        /// </summary>
450        /// <param name="length"></param>
451        /// <exception cref="NotSupportedException">No default n-gram frequencies available</exception>
452        /// <returns></returns>
453        private string GetStatisticsFilename(int length)
454        {
455            if (length < 1)
456            {
457                throw new ArgumentOutOfRangeException("There is no known default statistic for an n-gram length of " + length);
458            }
459
460            return "Enigma_" + length + "gram_Frequency.txt";
461        }
462        public string ByteArrayToString(byte[] arr)
463        {
464            System.Text.ASCIIEncoding enc = new System.Text.ASCIIEncoding();
465            return enc.GetString(arr);
466        }
467
468
469        #endregion
470
471     
472    }
473
474    #region slave
475
476    public class CostFunctionControl : IControlCost
477    {
478        public event IControlStatusChangedEventHandler OnStatusChanged;
479        #region IControlCost Members
480
481        private CostFunction plugin;
482
483        #endregion
484
485        /// <summary>
486        /// Constructor
487        /// </summary>
488        /// <param name="plugin"></param>
489        public CostFunctionControl(CostFunction plugin)
490        {
491            this.plugin = plugin;
492        }
493
494        public int getBytesToUse()
495        {
496            try
497            {
498                return int.Parse(((CostFunctionSettings)this.plugin.Settings).BytesToUse);
499            }
500            catch (Exception ex)
501            {
502                throw new Exception("Entered bytesToUse is not an integer: " + ex.Message);
503            }
504        }
505
506        /// <summary>
507        /// Returns the relation operator of the cost function which is set by by CostFunctionSettings
508        /// </summary>
509        /// <returns>RelationOperator</returns>
510        public RelationOperator getRelationOperator()
511        {
512            switch (((CostFunctionSettings)this.plugin.Settings).FunctionType)
513            {
514                case 0: //Index of coincidence
515                    return RelationOperator.LargerThen;
516                case 1: //Entropy
517                    return RelationOperator.LessThen;
518                case 2: // Bigrams: log 2
519                    return RelationOperator.LargerThen;
520                default:
521                    throw new NotImplementedException("The value " + ((CostFunctionSettings)this.plugin.Settings).FunctionType + " is not implemented.");
522            }//end switch
523        }//end getRelationOperator
524
525        /// <summary>
526        /// Calculates the cost function of the given text
527        ///
528        /// Cost function can be set by CostFunctionSettings
529        /// This algorithm uses a bytesToUse which can be set by CostFunctionSettings
530        /// If bytesToUse is set to 0 it uses the whole text
531        ///
532        /// </summary>
533        /// <param name="text"></param>
534        /// <returns>cost</returns>
535        public double calculateCost(byte[] text)
536        {
537            int bytesToUse = 0;
538            try
539            {
540                bytesToUse = int.Parse(((CostFunctionSettings)this.plugin.Settings).BytesToUse);
541            }
542            catch (Exception ex)
543            {
544                throw new Exception("Entered bytesToUse is not an integer: " + ex.Message);
545            }
546
547            switch (((CostFunctionSettings)this.plugin.Settings).FunctionType)
548            {
549                case 0: //Index of coincidence
550                    return plugin.calculateIndexOfCoincidence(text, bytesToUse);
551                case 1: //Entropy
552                    return plugin.calculateEntropy(text, bytesToUse);
553                case 2: // Bigrams: log 2
554                    return plugin.calculateNGrams(plugin.ByteArrayToString(text), 2, 2);
555                case 3: // Bigrams: Sinkov
556                    return plugin.calculateNGrams(plugin.ByteArrayToString(text), 2, 3);
557                case 4: // Bigrams: Percentaged
558                    return plugin.calculateNGrams(plugin.ByteArrayToString(text), 2, 1);
559                default:
560                    throw new NotImplementedException("The value " + ((CostFunctionSettings)this.plugin.Settings).FunctionType + " is not implemented.");
561            }//end switch
562        }
563
564        #endregion
565    }
566   
567}
568
Note: See TracBrowser for help on using the repository browser.