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

Last change on this file since 848 was 848, checked in by malischewski, 12 years ago

Added Cost-functions: Bigram log 2, sinkov, percentaged from Enigma Plugin (These use Enigma_*gram_Frequency.txt at the moment)

File size: 17.9 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
277            double[] n = new double[256];
278            //count all ASCII symbols
279            foreach (byte b in text)
280            {
281                    n[b]++;
282            }
283
284            double coindex = 0;
285            //sum them
286            for (int i = 0; i < n.Length; i++)
287            {
288                coindex = coindex + n[i] * (n[i] - 1);               
289            }
290
291            coindex = coindex / (text.Length);
292            coindex = coindex / (text.Length - 1);
293
294            return coindex * 100;
295
296        }//end calculateIndexOfCoincidence
297
298        /// <summary>
299        /// Calculates the Entropy of a given byte array
300        /// for example a German text has about 4.0629
301        /// </summary>
302        /// <param name="text">text to use</param>
303        /// <returns>Entropy</returns>
304        public double calculateEntropy(byte[] text)
305        {
306
307            double[] n = new double[256];
308            //count all ASCII symbols
309            foreach (byte b in text)
310            {
311                    n[b]++;
312            }
313
314            double entropy = 0;
315            //calculate probabilities and sum entropy
316            for (int i = 0; i < n.Length; i++)
317            {
318                double pz = n[i] / text.Length; //probability of character n[i]
319                if (pz > 0)
320                    entropy = entropy + pz * Math.Log(pz, 2);
321            }
322
323            return -1 * entropy; // because of log we have negative values, but we want positive
324
325        }//end calculateEntropy
326
327
328        /// <summary>
329        /// This method calculates a trigram log2 score of a given text on the basis of a given grams dictionary.
330        /// Case is insensitive.
331        /// </summary>
332        /// <param name="input">The text to be scored</param>
333        /// <param name="length">n-gram length</param>
334        /// <returns>The trigram score result</returns>
335        public double calculateNGrams(string input, int length, int valueSelection)
336        {
337            this.statistics = new Dictionary<int, IDictionary<string, double[]>>();
338            double score = 0;
339            IDictionary<string, double[]> corpusGrams = GetStatistics(length);
340
341            // FIXME: case handling?
342
343            HashSet<string> inputGrams = new HashSet<string>();
344
345            foreach (string g in GramTokenizer.tokenize(input, length, false))
346            {
347                // ensure each n-gram is counted only once
348                if (inputGrams.Add(g))
349                {
350                    if (corpusGrams.ContainsKey(g))
351                    {
352                        score += corpusGrams[g][valueSelection];
353                        GuiLogMessage(input, NotificationLevel.Info);
354           
355                    }
356                }
357            }
358            return score;
359        }
360        public IDictionary<string, double[]> GetStatistics(int gramLength)
361        {
362            // FIXME: inputTriGrams is not being used!
363
364            // FIXME: implement exception handling
365            if (!statistics.ContainsKey(gramLength))
366            {
367                GuiLogMessage("Trying to load default statistics for " + gramLength + "-grams", NotificationLevel.Info);
368                statistics[gramLength] = LoadDefaultStatistics(gramLength);               
369            }
370
371            return statistics[gramLength];
372        }
373
374
375        private IDictionary<string, double[]> LoadDefaultStatistics(int length)
376        {
377            Dictionary<string, double[]> grams = new Dictionary<string, double[]>();
378
379            StreamReader reader = new StreamReader(Path.Combine(PluginResource.directoryPath, GetStatisticsFilename(length)));
380
381            string line;
382            while ((line = reader.ReadLine()) != null)
383            {
384                if (line.StartsWith("#"))
385                    continue;
386
387                string[] tokens = WordTokenizer.tokenize(line).ToArray();
388                if (tokens.Length == 0)
389                    continue;
390                //Debug.Assert(tokens.Length == 2, "Expected 2 tokens, found " + tokens.Length + " on one line");
391
392                grams.Add(tokens[0], new double[] { Double.Parse(tokens[1]), 0, 0, 0 });
393            }
394
395            double sum = grams.Values.Sum(item => item[ABSOLUTE]);
396            GuiLogMessage("Sum of all n-gram counts is: " + sum, NotificationLevel.Debug);
397
398            // calculate scaled values
399            foreach (double[] g in grams.Values)
400            {
401                g[PERCENTAGED] = g[ABSOLUTE] / sum;
402                g[LOG2] = Math.Log(g[ABSOLUTE], 2);
403                g[SINKOV] = Math.Log(g[PERCENTAGED], Math.E);
404            }
405
406            return grams;
407        }
408
409        /// <summary>
410        /// Get file name for default n-gram frequencies.
411        /// </summary>
412        /// <param name="length"></param>
413        /// <exception cref="NotSupportedException">No default n-gram frequencies available</exception>
414        /// <returns></returns>
415        private string GetStatisticsFilename(int length)
416        {
417            if (length < 1)
418            {
419                throw new ArgumentOutOfRangeException("There is no known default statistic for an n-gram length of " + length);
420            }
421
422            return "Enigma_" + length + "gram_Frequency.txt";
423        }
424        public string ByteArrayToString(byte[] arr)
425        {
426            System.Text.ASCIIEncoding enc = new System.Text.ASCIIEncoding();
427            return enc.GetString(arr);
428        }
429
430
431        #endregion
432
433     
434    }
435
436    #region slave
437
438    public class CostFunctionControl : IControlCost
439    {
440        public event IControlStatusChangedEventHandler OnStatusChanged;
441        #region IControlCost Members
442
443        private CostFunction plugin;
444
445        #endregion
446
447        /// <summary>
448        /// Constructor
449        /// </summary>
450        /// <param name="plugin"></param>
451        public CostFunctionControl(CostFunction plugin)
452        {
453            this.plugin = plugin;
454        }
455
456        public int getBytesToUse()
457        {
458            try
459            {
460                return int.Parse(((CostFunctionSettings)this.plugin.Settings).BytesToUse);
461            }
462            catch (Exception ex)
463            {
464                throw new Exception("Entered bytesToUse is not an integer: " + ex.Message);
465            }
466        }
467
468        /// <summary>
469        /// Returns the relation operator of the cost function which is set by by CostFunctionSettings
470        /// </summary>
471        /// <returns>RelationOperator</returns>
472        public RelationOperator getRelationOperator()
473        {
474            switch (((CostFunctionSettings)this.plugin.Settings).FunctionType)
475            {
476                case 0: //Index of coincidence
477                    return RelationOperator.LargerThen;
478                case 1: //Entropy
479                    return RelationOperator.LessThen;
480                case 2: // Bigrams: log 2
481                    return RelationOperator.LargerThen;
482                default:
483                    throw new NotImplementedException("The value " + ((CostFunctionSettings)this.plugin.Settings).FunctionType + " is not implemented.");
484            }//end switch
485        }//end getRelationOperator
486
487        /// <summary>
488        /// Calculates the cost function of the given text
489        ///
490        /// Cost function can be set by CostFunctionSettings
491        /// This algorithm uses a bytesToUse which can be set by CostFunctionSettings
492        /// If bytesToUse is set to 0 it uses the whole text
493        ///
494        /// </summary>
495        /// <param name="text"></param>
496        /// <returns>cost</returns>
497        public double calculateCost(byte[] text)
498        {
499            int bytesToUse = 0;
500            try
501            {
502                bytesToUse = int.Parse(((CostFunctionSettings)this.plugin.Settings).BytesToUse);
503            }
504            catch (Exception ex)
505            {
506                throw new Exception("Entered bytesToUse is not an integer: " + ex.Message);
507            }
508           
509            if (bytesToUse > text.Length)
510                bytesToUse = 0;
511
512            byte[] array;
513
514            if (bytesToUse > 0)
515            {
516                //Create a new Array of size of bytesToUse if needed
517                array = new byte[bytesToUse];
518                for (int i = 0; i < bytesToUse && i < text.Length; i++)
519                {
520                    array[i] = text[i];
521                }
522            }
523            else
524            {
525                array = text;
526            }
527
528            switch (((CostFunctionSettings)this.plugin.Settings).FunctionType)
529            {
530                case 0: //Index of coincidence
531                    return plugin.calculateIndexOfCoincidence(array);
532                case 1: //Entropy
533                    return plugin.calculateEntropy(array);
534                case 2: // Bigrams: log 2
535                    return plugin.calculateNGrams(plugin.ByteArrayToString(array), 2, 2);
536                case 3: // Bigrams: Sinkov
537                    return plugin.calculateNGrams(plugin.ByteArrayToString(array), 2, 3);
538                case 4: // Bigrams: Percentaged
539                    return plugin.calculateNGrams(plugin.ByteArrayToString(array), 2, 1);
540                default:
541                    throw new NotImplementedException("The value " + ((CostFunctionSettings)this.plugin.Settings).FunctionType + " is not implemented.");
542            }//end switch
543        }
544
545        #endregion
546    }
547   
548}
549
Note: See TracBrowser for help on using the repository browser.