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

Last change on this file since 1208 was 1208, checked in by Sven Rech, 12 years ago

little bit faster entropy implementation

File size: 21.2 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;
28using System.Text.RegularExpressions;
29using System.Threading;
30namespace Cryptool.Plugins.CostFunction
31{
32    [Author("Nils Kopal", "Nils.Kopal@cryptool.org", "Uni Duisburg-Essen", "http://www.uni-due.de")]
33    [PluginInfo(false, "CostFunction", "CostFunction", null, "CostFunction/icon.png")]
34    public class CostFunction : IAnalysisMisc
35    {
36        #region private variables
37        private CostFunctionSettings settings = new CostFunctionSettings();
38        private byte[] inputText = null;
39        private byte[] outputText = null;
40        private double value = 0;
41        private Boolean stopped = true;
42        private IControlCost controlSlave;
43        private String bigramInput;
44        private double[,] bigramMatrix;
45        private IDictionary<string, double[]> corpusGrams;
46
47        private DataManager dataMgr = new DataManager();
48        private const string DATATYPE = "transposition";
49
50        private IDictionary<String, DataFileMetaInfo> txtList;
51        private IDictionary<int, IDictionary<string, double[]>> statistics;
52
53        #endregion
54        #region internal constants
55        internal const int ABSOLUTE = 0;
56        internal const int PERCENTAGED = 1;
57        internal const int LOG2 = 2;
58        internal const int SINKOV = 3;
59        #endregion
60        #region CostFunctionInOut
61
62        [PropertyInfo(Direction.InputData, "Text Input", "Input your Text here", "", DisplayLevel.Beginner)]
63        public byte[] InputText
64        {
65            get
66            {
67                return inputText;
68            }
69            set
70            {
71                this.inputText = value;
72                OnPropertyChanged("InputText");
73            }
74        }
75
76        [PropertyInfo(Direction.OutputData, "Text Output", "Your Text will be send here", "", DisplayLevel.Beginner)]
77        public byte[] OutputText
78        {
79            get
80            {
81                return outputText;
82            }
83            set
84            {
85                this.outputText = value;
86                OnPropertyChanged("OutputText");
87            }
88        }
89
90        [PropertyInfo(Direction.OutputData, "Value", "The value of the function will be send here", "", DisplayLevel.Beginner)]
91        public double Value
92        {
93            get
94            {
95                return value;
96            }
97            set
98            {
99                this.value = value;
100                OnPropertyChanged("Value");
101            }
102        }
103
104        [PropertyInfo(Direction.ControlSlave, "SDES Slave", "Direct access to SDES.", "", DisplayLevel.Beginner)]
105        public IControlCost ControlSlave
106        {
107            get
108            {
109                if (controlSlave == null)
110                    controlSlave = new CostFunctionControl(this);
111                return controlSlave;
112            }
113        }
114
115        #endregion
116
117        #region IPlugin Members
118
119        public event GuiLogNotificationEventHandler OnGuiLogNotificationOccured;
120        public event PluginProgressChangedEventHandler OnPluginProgressChanged;
121
122
123        public ISettings Settings
124        {
125            get { return this.settings; }
126            set { this.settings = (CostFunctionSettings)value; }
127        }
128
129        public System.Windows.Controls.UserControl Presentation
130        {
131            get { return null; }
132        }
133
134        public System.Windows.Controls.UserControl QuickWatchPresentation
135        {
136            get { return null; }
137        }
138
139        public void PreExecution()
140        {
141            this.stopped = false;
142        }
143
144        public void Execute()
145        {
146            if (this.InputText is Object && this.stopped == false)
147            {
148                int bytesToUse = 0;
149                try
150                {
151                    bytesToUse = int.Parse(settings.BytesToUse);
152                }
153                catch (Exception ex)
154                {
155                    GuiLogMessage("Entered bytesToUse is not an integer: " + ex.Message, NotificationLevel.Error);
156                    return;
157                }
158
159                if (bytesToUse > this.InputText.Length)
160                {
161                    bytesToUse = 0;
162                }
163
164                byte[] array;
165
166                if (bytesToUse > 0)
167                {
168                    //Create a new Array of size of bytesToUse if needed
169                    array = new byte[bytesToUse];
170                    for (int i = 0; i < bytesToUse && i < this.InputText.Length; i++)
171                    {
172                        array[i] = InputText[i];
173                    }
174                }
175                else
176                {
177                    array = this.InputText;
178                }
179
180                ProgressChanged(0.5, 1);
181                bigramInput = ByteArrayToString(array);
182                switch (settings.FunctionType)
183                {
184
185                    case 0: // Index of Coincedence
186                        this.Value = calculateIndexOfCoincidence(array);
187                        break;
188
189                    case 1: // Entropy
190                        this.Value = calculateEntropy(array);
191                        break;
192
193                    case 2: // Log 2 Bigrams
194                        this.Value = calculateNGrams(bigramInput, 2, 2);
195                        break;
196
197                    case 3: // sinkov Bigrams
198                        this.Value = calculateNGrams(bigramInput, 2, 3);
199                        break;
200                    case 4: //percentaged Bigrams
201                        this.Value = calculateNGrams(bigramInput, 2, 1);
202                        break;
203                    case 5: //regular expressions
204                        this.Value = regex(bigramInput);
205                        break;
206                    default:
207                        this.Value = -1;
208                        break;
209                }//end switch               
210
211                this.OutputText = this.InputText;
212                ProgressChanged(1, 1);
213
214            }//end if
215
216        }//end Execute
217
218
219        public void PostExecution()
220        {
221            this.stopped = true;
222        }
223
224        public void Pause()
225        {
226
227        }
228
229        public void Stop()
230        {
231            this.stopped = false;
232        }
233
234        public void Initialize()
235        {
236
237        }
238
239        public void Dispose()
240        {
241
242        }
243
244        #endregion
245
246        #region INotifyPropertyChanged Members
247
248        public event System.ComponentModel.PropertyChangedEventHandler PropertyChanged;
249
250        public void OnPropertyChanged(string name)
251        {
252            EventsHelper.PropertyChanged(PropertyChanged, this, new PropertyChangedEventArgs(name));
253        }
254
255        private void ProgressChanged(double value, double max)
256        {
257            EventsHelper.ProgressChanged(OnPluginProgressChanged, this, new PluginProgressEventArgs(value, max));
258        }
259
260        public void GuiLogMessage(string p, NotificationLevel notificationLevel)
261        {
262            EventsHelper.GuiLogMessage(OnGuiLogNotificationOccured, this, new GuiLogEventArgs(p, this, notificationLevel));
263        }
264
265        #endregion
266
267        #region IPlugin Members
268
269        public event StatusChangedEventHandler OnPluginStatusChanged;
270
271        #endregion
272
273        #region private methods
274
275
276        //public double contains(string input)
277        //{
278        //    if (settings.Contains == null)
279        //    {
280        //        GuiLogMessage("There is no text to be searched for. Please insert text in the 'Contains text / Regular Expression' - Textarea", NotificationLevel.Error);
281        //        return new Double();
282        //    }
283
284        //    if (input.Contains(settings.Contains))
285        //    {
286        //        return 1.0;
287        //    }
288        //    return -1.0;
289        //}
290
291        public double regex(string input)
292        {
293            if (settings.RegEx == null)
294            {
295                GuiLogMessage("There is no Regular Expression to be searched for. Please insert regex in the 'Regular Expression' - Textarea", NotificationLevel.Error);
296                return new Double();
297            }
298            try
299            {
300                Match match = Regex.Match(input, settings.RegEx);
301                if (match.Success)
302                {
303                    return 1.0;
304                }
305                else
306                {
307                    return -1.0;
308                }
309            }
310            catch (Exception e)
311            {
312                GuiLogMessage(e.Message, NotificationLevel.Error);
313                return -1.0;
314            }
315
316        }
317
318
319        /// <summary>
320        /// Calculates the Index of Coincidence multiplied with 100 of
321        /// a given byte array
322        ///
323        /// for example a German text has about 7.62
324        ///           an English text has about 6.61
325        /// </summary>
326        /// <param name="text">text to use</param>
327        /// <returns>Index of Coincidence</returns>
328        public double calculateIndexOfCoincidence(byte[] text)
329        {
330            return calculateIndexOfCoincidence(text, text.Length);
331        }
332
333        /// <summary>
334        /// Calculates the Index of Coincidence multiplied with 100 of
335        /// a given byte array
336        ///
337        /// for example a German text has about 7.62
338        ///           an English text has about 6.61
339        /// </summary>
340        /// <param name="text">text to use</param>
341        /// <param name="text">bytesToUse</param>
342        /// <returns>Index of Coincidence</returns>
343        public double calculateIndexOfCoincidence(byte[] text, int bytesToUse)
344        {           
345            if (bytesToUse > text.Length)
346                bytesToUse = text.Length;
347
348            double[] n = new double[256];
349            //count all ASCII symbols
350            int counter = 0;
351            foreach (byte b in text)
352            {
353                n[b]++;
354                counter++;
355                if (counter == bytesToUse)
356                    break;
357            }
358
359            double coindex = 0;
360            //sum them
361            for (int i = 0; i < n.Length; i++)
362            {
363                coindex = coindex + n[i] * (n[i] - 1);
364            }
365
366            coindex = coindex / (bytesToUse);
367            coindex = coindex / (bytesToUse - 1);
368
369            return coindex * 100;
370
371        }//end calculateIndexOfCoincidence
372
373
374        private int lastUsedSize = -1;
375        private double[] xlogx;
376        private Mutex prepareMutex = new Mutex();
377
378        private void prepareEntropy(int size)
379        {
380            xlogx = new double[size + 1];
381            //precomputations for fast entropy calculation     
382            xlogx[0] = 0.0;
383            for (int i = 1; i <= size; i++)
384                xlogx[i] = -1.0 * i * Math.Log(i / (double)size) / Math.Log(2.0);
385        }
386
387        /// <summary>
388        /// Calculates the Entropy of a given byte array
389        /// for example a German text has about 4.0629
390        /// </summary>
391        /// <param name="text">text to use</param>
392        /// <returns>Entropy</returns>
393        public double calculateEntropy(byte[] text)
394        {
395            return calculateEntropy(text, text.Length);
396        }
397
398        /// <summary>
399        /// Calculates the Entropy of a given byte array
400        /// for example a German text has about 4.0629
401        /// </summary>
402        /// <param name="text">text to use</param>
403        /// <returns>Entropy</returns>
404        public double calculateEntropy(byte[] text, int bytesToUse)
405        {
406            return NativeCryptography.Crypto.calculateEntropy(text, bytesToUse);
407            if (bytesToUse > text.Length)
408                bytesToUse = text.Length;
409
410            if (lastUsedSize != bytesToUse)
411            {
412                try
413                {
414                    prepareMutex.WaitOne();
415                    if (lastUsedSize != bytesToUse)
416                    {
417                        prepareEntropy(bytesToUse);
418                        lastUsedSize = bytesToUse;
419                    }
420                }
421                finally
422                {
423                    prepareMutex.ReleaseMutex();
424                }
425            }
426
427            int[] n = new int[256];
428            //count all ASCII symbols
429            for (int counter = 0; counter < bytesToUse; counter++)
430            {
431                n[text[counter]]++;
432            }
433
434            double entropy = 0;
435            //calculate probabilities and sum entropy
436            for (int i = 0; i < 256; i++)
437                entropy += xlogx[n[i]];
438
439            return entropy / (double)bytesToUse;
440
441        }//end calculateEntropy
442
443        /// <summary>
444        /// This method calculates a trigram log2 score of a given text on the basis of a given grams dictionary.
445        /// Case is insensitive.
446        /// </summary>
447        /// <param name="input">The text to be scored</param>
448        /// <param name="length">n-gram length</param>
449        /// <returns>The trigram score result</returns>
450        public double calculateNGrams(string input, int length, int valueSelection)
451        {
452            this.statistics = new Dictionary<int, IDictionary<string, double[]>>();
453            double score = 0;
454            if (corpusGrams == null)
455            { corpusGrams = GetStatistics(length); }
456            input = input.ToUpper();
457            // FIXME: case handling?
458
459            HashSet<string> inputGrams = new HashSet<string>();
460
461            foreach (string g in GramTokenizer.tokenize(input, length, false))
462            {
463                // ensure each n-gram is counted only once
464                if (inputGrams.Add(g))
465                {
466                    if (corpusGrams.ContainsKey(g))
467                    {
468                        score += corpusGrams[g][valueSelection];
469
470                    }
471                }
472            }
473
474            return score;
475        }
476        public IDictionary<string, double[]> GetStatistics(int gramLength)
477        {
478            // FIXME: inputTriGrams is not being used!
479
480            // FIXME: implement exception handling
481            if (!statistics.ContainsKey(gramLength))
482            {
483                //GuiLogMessage("Trying to load default statistics for " + gramLength + "-grams", NotificationLevel.Info);
484                statistics[gramLength] = LoadDefaultStatistics(gramLength);
485            }
486
487            return statistics[gramLength];
488        }
489
490        private IDictionary<string, double[]> LoadDefaultStatistics(int length)
491        {
492            txtList = dataMgr.LoadDirectory(DATATYPE);
493
494            return calculateAbsolutes(txtList["2gram.txt"].DataFile.FullName);
495        }
496
497        private IDictionary<string, double[]> calculateAbsolutes(String path)
498        {
499
500
501            Dictionary<string, double[]> grams = new Dictionary<string, double[]>();
502
503            StreamReader reader = new StreamReader(path);
504            String text = reader.ReadToEnd();
505
506            text.ToUpper();
507            text = Regex.Replace(text, "[^A-Z]*", "");
508
509
510            for (int i = 0; i < text.Length - 1; i++)
511            {
512                char a = text[i];
513                char b = text[i + 1];
514                String key = a.ToString();
515                key = key + b.ToString();
516
517                if (!grams.ContainsKey(key))
518                {
519                    grams.Add(key, new double[] { 1, 0, 0, 0 });
520                }
521                else
522                {
523                    grams[key][0] = grams[key][0] + 1.0;
524                }
525            }
526
527            double sum = grams.Values.Sum(item => item[ABSOLUTE]);
528            GuiLogMessage("Sum of all n-gram counts is: " + sum, NotificationLevel.Debug);
529
530            // calculate scaled values
531            foreach (double[] g in grams.Values)
532            {
533                g[PERCENTAGED] = g[ABSOLUTE] / sum;
534                g[LOG2] = Math.Log(g[ABSOLUTE], 2);
535                g[SINKOV] = Math.Log(g[PERCENTAGED], Math.E);
536            }
537
538
539
540            return grams;
541        }
542
543        public string ByteArrayToString(byte[] arr)
544        {
545            System.Text.ASCIIEncoding enc = new System.Text.ASCIIEncoding();
546            return enc.GetString(arr);
547        }
548
549
550        #endregion
551
552
553    }
554
555    #region slave
556
557    public class CostFunctionControl : IControlCost
558    {
559        public event IControlStatusChangedEventHandler OnStatusChanged;
560        #region IControlCost Members
561
562        private CostFunction plugin;
563
564        #endregion
565
566        /// <summary>
567        /// Constructor
568        /// </summary>
569        /// <param name="plugin"></param>
570        public CostFunctionControl(CostFunction plugin)
571        {
572            this.plugin = plugin;
573        }
574
575        public int getBytesToUse()
576        {
577            try
578            {
579                return int.Parse(((CostFunctionSettings)this.plugin.Settings).BytesToUse);
580            }
581            catch (Exception ex)
582            {
583                throw new Exception("Entered bytesToUse is not an integer: " + ex.Message);
584            }
585        }
586
587        /// <summary>
588        /// Returns the relation operator of the cost function which is set by by CostFunctionSettings
589        /// </summary>
590        /// <returns>RelationOperator</returns>
591        public RelationOperator getRelationOperator()
592        {
593            switch (((CostFunctionSettings)this.plugin.Settings).FunctionType)
594            {
595                case 0: //Index of coincidence
596                    return RelationOperator.LargerThen;
597                case 1: //Entropy
598                    return RelationOperator.LessThen;
599                case 2: // Bigrams: log 2
600                    return RelationOperator.LessThen;
601                case 3: // Sinkov
602                    return RelationOperator.LargerThen;
603                case 4: // percentage
604                    return RelationOperator.LargerThen;
605                case 5: // Regular Expression
606                    return RelationOperator.LargerThen;
607                default:
608                    throw new NotImplementedException("The value " + ((CostFunctionSettings)this.plugin.Settings).FunctionType + " is not implemented.");
609            }//end switch
610        }//end getRelationOperator
611
612        /// <summary>
613        /// Calculates the cost function of the given text
614        ///
615        /// Cost function can be set by CostFunctionSettings
616        /// This algorithm uses a bytesToUse which can be set by CostFunctionSettings
617        /// If bytesToUse is set to 0 it uses the whole text
618        ///
619        /// </summary>
620        /// <param name="text"></param>
621        /// <returns>cost</returns>
622        public double calculateCost(byte[] text)
623        {
624            int bytesToUse = 0;
625            try
626            {
627                bytesToUse = ((CostFunctionSettings)this.plugin.Settings).BytesToUseInteger;
628            }
629            catch (Exception ex)
630            {
631                throw new Exception("Entered bytesToUse is not an integer: " + ex.Message);
632            }
633
634            switch (((CostFunctionSettings)this.plugin.Settings).FunctionType)
635            {
636                case 0: //Index of coincidence
637                    return plugin.calculateIndexOfCoincidence(text, bytesToUse);
638                case 1: //Entropy
639                    return plugin.calculateEntropy(text, bytesToUse);
640                case 2: // Bigrams: log 2
641                    return plugin.calculateNGrams(plugin.ByteArrayToString(text), 2, 2);
642                case 3: // Bigrams: Sinkov
643                    return plugin.calculateNGrams(plugin.ByteArrayToString(text), 2, 3);
644                case 4: // Bigrams: Percentaged
645                    return plugin.calculateNGrams(plugin.ByteArrayToString(text), 2, 1);
646                case 5: // regular expression
647                    return plugin.regex(plugin.ByteArrayToString(text));
648                default:
649                    throw new NotImplementedException("The value " + ((CostFunctionSettings)this.plugin.Settings).FunctionType + " is not implemented.");
650            }//end switch
651        }
652
653
654    #endregion
655    }
656
657}
658
Note: See TracBrowser for help on using the repository browser.